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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [web.c] - Blame information for rev 859

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

Line No. Rev Author Line
1 280 jeremybenn
/* 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
 

powered by: WebSVN 2.1.0

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