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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [ipa-utils.c] - Blame information for rev 154

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Utilities for ipa analysis.
2
   Copyright (C) 2005, 2007 Free Software Foundation, Inc.
3
   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
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
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "tree.h"
26
#include "tree-flow.h"
27
#include "tree-inline.h"
28
#include "tree-pass.h"
29
#include "langhooks.h"
30
#include "pointer-set.h"
31
#include "ggc.h"
32
#include "ipa-utils.h"
33
#include "ipa-reference.h"
34
#include "c-common.h"
35
#include "tree-gimple.h"
36
#include "cgraph.h"
37
#include "output.h"
38
#include "flags.h"
39
#include "timevar.h"
40
#include "diagnostic.h"
41
#include "langhooks.h"
42
 
43
/* Debugging function for postorder and inorder code. NOTE is a string
44
   that is printed before the nodes are printed.  ORDER is an array of
45
   cgraph_nodes that has COUNT useful nodes in it.  */
46
 
47
void
48
ipa_utils_print_order (FILE* out,
49
                       const char * note,
50
                       struct cgraph_node** order,
51
                       int count)
52
{
53
  int i;
54
  fprintf (out, "\n\n ordered call graph: %s\n", note);
55
 
56
  for (i = count - 1; i >= 0; i--)
57
    dump_cgraph_node(dump_file, order[i]);
58
  fprintf (out, "\n");
59
  fflush(out);
60
}
61
 
62
 
63
struct searchc_env {
64
  struct cgraph_node **stack;
65
  int stack_size;
66
  struct cgraph_node **result;
67
  int order_pos;
68
  splay_tree nodes_marked_new;
69
  bool reduce;
70
  int count;
71
};
72
 
73
/* This is an implementation of Tarjan's strongly connected region
74
   finder as reprinted in Aho Hopcraft and Ullman's The Design and
75
   Analysis of Computer Programs (1975) pages 192-193.  This version
76
   has been customized for cgraph_nodes.  The env parameter is because
77
   it is recursive and there are no nested functions here.  This
78
   function should only be called from itself or
79
   cgraph_reduced_inorder.  ENV is a stack env and would be
80
   unnecessary if C had nested functions.  V is the node to start
81
   searching from.  */
82
 
83
static void
84
searchc (struct searchc_env* env, struct cgraph_node *v)
85
{
86
  struct cgraph_edge *edge;
87
  struct ipa_dfs_info *v_info = v->aux;
88
 
89
  /* mark node as old */
90
  v_info->new = false;
91
  splay_tree_remove (env->nodes_marked_new, v->uid);
92
 
93
  v_info->dfn_number = env->count;
94
  v_info->low_link = env->count;
95
  env->count++;
96
  env->stack[(env->stack_size)++] = v;
97
  v_info->on_stack = true;
98
 
99
  for (edge = v->callees; edge; edge = edge->next_callee)
100
    {
101
      struct ipa_dfs_info * w_info;
102
      struct cgraph_node *w = edge->callee;
103
      /* Bypass the clones and only look at the master node.  Skip
104
         external and other bogus nodes.  */
105
      w = cgraph_master_clone (w);
106
      if (w && w->aux)
107
        {
108
          w_info = w->aux;
109
          if (w_info->new)
110
            {
111
              searchc (env, w);
112
              v_info->low_link =
113
                (v_info->low_link < w_info->low_link) ?
114
                v_info->low_link : w_info->low_link;
115
            }
116
          else
117
            if ((w_info->dfn_number < v_info->dfn_number)
118
                && (w_info->on_stack))
119
              v_info->low_link =
120
                (w_info->dfn_number < v_info->low_link) ?
121
                w_info->dfn_number : v_info->low_link;
122
        }
123
    }
124
 
125
 
126
  if (v_info->low_link == v_info->dfn_number)
127
    {
128
      struct cgraph_node *last = NULL;
129
      struct cgraph_node *x;
130
      struct ipa_dfs_info *x_info;
131
      do {
132
        x = env->stack[--(env->stack_size)];
133
        x_info = x->aux;
134
        x_info->on_stack = false;
135
 
136
        if (env->reduce)
137
          {
138
            x_info->next_cycle = last;
139
            last = x;
140
          }
141
        else
142
          env->result[env->order_pos++] = x;
143
      }
144
      while (v != x);
145
      if (env->reduce)
146
        env->result[env->order_pos++] = v;
147
    }
148
}
149
 
150
/* Topsort the call graph by caller relation.  Put the result in ORDER.
151
 
152
   The REDUCE flag is true if you want the cycles reduced to single
153
   nodes.  Only consider nodes that have the output bit set. */
154
 
155
int
156
ipa_utils_reduced_inorder (struct cgraph_node **order,
157
                           bool reduce, bool allow_overwritable)
158
{
159
  struct cgraph_node *node;
160
  struct searchc_env env;
161
  splay_tree_node result;
162
  env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
163
  env.stack_size = 0;
164
  env.result = order;
165
  env.order_pos = 0;
166
  env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
167
  env.count = 1;
168
  env.reduce = reduce;
169
 
170
  for (node = cgraph_nodes; node; node = node->next)
171
    if ((node->analyzed)
172
        && (cgraph_is_master_clone (node)
173
         || (allow_overwritable
174
             && (cgraph_function_body_availability (node) ==
175
                 AVAIL_OVERWRITABLE))))
176
      {
177
        /* Reuse the info if it is already there.  */
178
        struct ipa_dfs_info *info = node->aux;
179
        if (!info)
180
          info = xcalloc (1, sizeof (struct ipa_dfs_info));
181
        info->new = true;
182
        info->on_stack = false;
183
        info->next_cycle = NULL;
184
        node->aux = info;
185
 
186
        splay_tree_insert (env.nodes_marked_new,
187
                           (splay_tree_key)node->uid,
188
                           (splay_tree_value)node);
189
      }
190
    else
191
      node->aux = NULL;
192
  result = splay_tree_min (env.nodes_marked_new);
193
  while (result)
194
    {
195
      node = (struct cgraph_node *)result->value;
196
      searchc (&env, node);
197
      result = splay_tree_min (env.nodes_marked_new);
198
    }
199
  splay_tree_delete (env.nodes_marked_new);
200
  free (env.stack);
201
 
202
  return env.order_pos;
203
}
204
 
205
 
206
/* Given a memory reference T, will return the variable at the bottom
207
   of the access.  Unlike get_base_address, this will recurse thru
208
   INDIRECT_REFS.  */
209
 
210
tree
211
get_base_var (tree t)
212
{
213
  if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
214
    return t;
215
 
216
  while (!SSA_VAR_P (t)
217
         && (!CONSTANT_CLASS_P (t))
218
         && TREE_CODE (t) != LABEL_DECL
219
         && TREE_CODE (t) != FUNCTION_DECL
220
         && TREE_CODE (t) != CONST_DECL)
221
    {
222
      t = TREE_OPERAND (t, 0);
223
    }
224
  return t;
225
}
226
 

powered by: WebSVN 2.1.0

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