OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [web.c] - Blame information for rev 304

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Web construction code for GNU compiler.
2
   Contributed by Jan Hubicka.
3
   Copyright (C) 2001, 2002, 2004, 2006, 2007 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
    - Add code to keep debugging up-to-date after splitting user variable
31
      pseudos.  This can be done by keeping track of all the pseudos used
32
      for the variable and using life analysis information before reload
33
      to determine which one is live and, in case more than one are live,
34
      choose the one with the latest definition.
35
 
36
      Other optimization passes can benefit from the infrastructure too.
37
 
38
    - We may use profile information and ignore infrequent use for the
39
      purpose of web unifying, inserting the compensation code later to
40
      implement full induction variable expansion for loops (currently
41
      we expand only if the induction variable is dead afterward, which
42
      is often the case).  */
43
 
44
#include "config.h"
45
#include "system.h"
46
#include "coretypes.h"
47
#include "tm.h"
48
#include "toplev.h"
49
 
50
#include "rtl.h"
51
#include "hard-reg-set.h"
52
#include "flags.h"
53
#include "obstack.h"
54
#include "basic-block.h"
55
#include "output.h"
56
#include "df.h"
57
#include "function.h"
58
#include "timevar.h"
59
#include "tree-pass.h"
60
 
61
 
62
static rtx entry_register (struct web_entry *, struct df_ref *, char *);
63
static void replace_ref (struct df_ref *, rtx);
64
 
65
/* Find the root of unionfind tree (the representative of set).  */
66
 
67
struct web_entry *
68
unionfind_root (struct web_entry *element)
69
{
70
  struct web_entry *element1 = element, *element2;
71
 
72
  while (element->pred)
73
    element = element->pred;
74
  while (element1->pred)
75
    {
76
      element2 = element1->pred;
77
      element1->pred = element;
78
      element1 = element2;
79
    }
80
  return element;
81
}
82
 
83
/* Union sets.
84
   Return true if FIRST and SECOND points to the same web entry structure and
85
   nothing is done.  Otherwise, return false.  */
86
 
87
bool
88
unionfind_union (struct web_entry *first, struct web_entry *second)
89
{
90
  first = unionfind_root (first);
91
  second = unionfind_root (second);
92
  if (first == second)
93
    return true;
94
  second->pred = first;
95
  return false;
96
}
97
 
98
/* For each use, all possible defs reaching it must come in the same
99
   register, union them.
100
   FUN is the function that does the union.  */
101
 
102
void
103
union_defs (struct df *df, struct df_ref *use, struct web_entry *def_entry,
104
            struct web_entry *use_entry,
105
            bool (*fun) (struct web_entry *, struct web_entry *))
106
{
107
  rtx insn = DF_REF_INSN (use);
108
  struct df_link *link = DF_REF_CHAIN (use);
109
  struct df_ref *use_link;
110
  struct df_ref *def_link;
111
  rtx set;
112
 
113
  if (insn)
114
    {
115
      use_link = DF_INSN_USES (df, insn);
116
      def_link = DF_INSN_DEFS (df, insn);
117
      set = single_set (insn);
118
    }
119
  else
120
    {
121
      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
  while (use_link)
132
    {
133
      if (use != use_link
134
          && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link))
135
        (*fun) (use_entry + DF_REF_ID (use),
136
                use_entry + DF_REF_ID (use_link));
137
      use_link = use_link->next_ref;
138
    }
139
 
140
  /* Recognize trivial noop moves and attempt to keep them as noop.
141
     While most of noop moves should be removed, we still keep some
142
     of them at libcall boundaries and such.  */
143
 
144
  if (set
145
      && SET_SRC (set) == DF_REF_REG (use)
146
      && SET_SRC (set) == SET_DEST (set))
147
    {
148
      while (def_link)
149
        {
150
          if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link))
151
            (*fun) (use_entry + DF_REF_ID (use),
152
                    def_entry + DF_REF_ID (def_link));
153
          def_link = def_link->next_ref;
154
        }
155
    }
156
  while (link)
157
    {
158
      (*fun) (use_entry + DF_REF_ID (use),
159
              def_entry + DF_REF_ID (link->ref));
160
      link = link->next;
161
    }
162
 
163
  /* A READ_WRITE use requires the corresponding def to be in the same
164
     register.  Find it and union.  */
165
  if (use->flags & DF_REF_READ_WRITE)
166
    {
167
      struct df_ref *link;
168
 
169
      if (DF_REF_INSN (use))
170
        link = DF_INSN_DEFS (df, DF_REF_INSN (use));
171
      else
172
        link = NULL;
173
 
174
      while (link)
175
        {
176
          if (DF_REF_REAL_REG (link) == DF_REF_REAL_REG (use))
177
            (*fun) (use_entry + DF_REF_ID (use),
178
                    def_entry + DF_REF_ID (link));
179
          link = link->next_ref;
180
        }
181
    }
182
}
183
 
184
/* Find the corresponding register for the given entry.  */
185
 
186
static rtx
187
entry_register (struct web_entry *entry, struct df_ref *ref, char *used)
188
{
189
  struct web_entry *root;
190
  rtx reg, newreg;
191
 
192
  /* Find the corresponding web and see if it has been visited.  */
193
  root = unionfind_root (entry);
194
  if (root->reg)
195
    return root->reg;
196
 
197
  /* We are seeing this web for the first time, do the assignment.  */
198
  reg = DF_REF_REAL_REG (ref);
199
 
200
  /* In case the original register is already assigned, generate new one.  */
201
  if (!used[REGNO (reg)])
202
    newreg = reg, used[REGNO (reg)] = 1;
203
  else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
204
    {
205
      newreg = reg;
206
      if (dump_file)
207
        fprintf (dump_file,
208
                 "New web forced to keep reg=%i (user variable)\n",
209
                 REGNO (reg));
210
    }
211
  else
212
    {
213
      newreg = gen_reg_rtx (GET_MODE (reg));
214
      REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
215
      REG_POINTER (newreg) = REG_POINTER (reg);
216
      REG_ATTRS (newreg) = REG_ATTRS (reg);
217
      if (dump_file)
218
        fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
219
                 REGNO (newreg));
220
    }
221
 
222
  root->reg = newreg;
223
  return newreg;
224
}
225
 
226
/* Replace the reference by REG.  */
227
 
228
static void
229
replace_ref (struct df_ref *ref, rtx reg)
230
{
231
  rtx oldreg = DF_REF_REAL_REG (ref);
232
  rtx *loc = DF_REF_REAL_LOC (ref);
233
 
234
  if (oldreg == reg)
235
    return;
236
  if (dump_file)
237
    fprintf (dump_file, "Updating insn %i (%i->%i)\n",
238
             INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg));
239
  *loc = reg;
240
}
241
 
242
/* Main entry point.  */
243
 
244
static void
245
web_main (void)
246
{
247
  struct df *df;
248
  struct web_entry *def_entry;
249
  struct web_entry *use_entry;
250
  unsigned int i;
251
  int max = max_reg_num ();
252
  char *used;
253
 
254
  df = df_init (DF_EQUIV_NOTES);
255
  df_chain_add_problem (df, DF_UD_CHAIN);
256
  df_analyze (df);
257
  df_reorganize_refs (&df->def_info);
258
  df_reorganize_refs (&df->use_info);
259
 
260
  def_entry = XCNEWVEC (struct web_entry, DF_DEFS_SIZE (df));
261
  use_entry = XCNEWVEC (struct web_entry, DF_USES_SIZE (df));
262
  used = XCNEWVEC (char, max);
263
 
264
  if (dump_file)
265
    df_dump (df, dump_file);
266
 
267
  /* Produce the web.  */
268
  for (i = 0; i < DF_USES_SIZE (df); i++)
269
    union_defs (df, DF_USES_GET (df, i), def_entry, use_entry, unionfind_union);
270
 
271
  /* Update the instruction stream, allocating new registers for split pseudos
272
     in progress.  */
273
  for (i = 0; i < DF_USES_SIZE (df); i++)
274
    replace_ref (DF_USES_GET (df, i),
275
                 entry_register (use_entry + i, DF_USES_GET (df, i), used));
276
  for (i = 0; i < DF_DEFS_SIZE (df); i++)
277
    replace_ref (DF_DEFS_GET (df, i),
278
                 entry_register (def_entry + i, DF_DEFS_GET (df, i), used));
279
 
280
  /* Dataflow information is corrupt here, but it can be easily updated
281
     by creating new entries for new registers and updates or calling
282
     df_insns_modify.  */
283
  free (def_entry);
284
  free (use_entry);
285
  free (used);
286
  df_finish (df);
287
  df = NULL;
288
}
289
 
290
static bool
291
gate_handle_web (void)
292
{
293
  return (optimize > 0 && flag_web);
294
}
295
 
296
static unsigned int
297
rest_of_handle_web (void)
298
{
299
  web_main ();
300
  delete_trivially_dead_insns (get_insns (), max_reg_num ());
301
  cleanup_cfg (CLEANUP_EXPENSIVE);
302
  reg_scan (get_insns (), max_reg_num ());
303
  return 0;
304
}
305
 
306
struct tree_opt_pass pass_web =
307
{
308
  "web",                                /* name */
309
  gate_handle_web,                      /* gate */
310
  rest_of_handle_web,                   /* execute */
311
  NULL,                                 /* sub */
312
  NULL,                                 /* next */
313
  0,                                    /* static_pass_number */
314
  TV_WEB,                               /* tv_id */
315
  0,                                    /* properties_required */
316
  0,                                    /* properties_provided */
317
  0,                                    /* properties_destroyed */
318
  0,                                    /* todo_flags_start */
319
  TODO_dump_func,                       /* todo_flags_finish */
320
  'Z'                                   /* letter */
321
};
322
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.