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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Utilities for ipa analysis.
2
   Copyright (C) 2005, 2007, 2008 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 "splay-tree.h"
32
#include "ggc.h"
33
#include "ipa-utils.h"
34
#include "ipa-reference.h"
35
#include "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
   ipa_utils_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
         bool (*ignore_edge) (struct cgraph_edge *))
86
{
87
  struct cgraph_edge *edge;
88
  struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
89
 
90
  /* mark node as old */
91
  v_info->new_node = false;
92
  splay_tree_remove (env->nodes_marked_new, v->uid);
93
 
94
  v_info->dfn_number = env->count;
95
  v_info->low_link = env->count;
96
  env->count++;
97
  env->stack[(env->stack_size)++] = v;
98
  v_info->on_stack = true;
99
 
100
  for (edge = v->callees; edge; edge = edge->next_callee)
101
    {
102
      struct ipa_dfs_info * w_info;
103
      struct cgraph_node *w = edge->callee;
104
 
105
      if (ignore_edge && ignore_edge (edge))
106
        continue;
107
 
108
      if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE)
109
        {
110
          w_info = (struct ipa_dfs_info *) w->aux;
111
          if (w_info->new_node)
112
            {
113
              searchc (env, w, ignore_edge);
114
              v_info->low_link =
115
                (v_info->low_link < w_info->low_link) ?
116
                v_info->low_link : w_info->low_link;
117
            }
118
          else
119
            if ((w_info->dfn_number < v_info->dfn_number)
120
                && (w_info->on_stack))
121
              v_info->low_link =
122
                (w_info->dfn_number < v_info->low_link) ?
123
                w_info->dfn_number : v_info->low_link;
124
        }
125
    }
126
 
127
 
128
  if (v_info->low_link == v_info->dfn_number)
129
    {
130
      struct cgraph_node *last = NULL;
131
      struct cgraph_node *x;
132
      struct ipa_dfs_info *x_info;
133
      do {
134
        x = env->stack[--(env->stack_size)];
135
        x_info = (struct ipa_dfs_info *) x->aux;
136
        x_info->on_stack = false;
137
 
138
        if (env->reduce)
139
          {
140
            x_info->next_cycle = last;
141
            last = x;
142
          }
143
        else
144
          env->result[env->order_pos++] = x;
145
      }
146
      while (v != x);
147
      if (env->reduce)
148
        env->result[env->order_pos++] = v;
149
    }
150
}
151
 
152
/* Topsort the call graph by caller relation.  Put the result in ORDER.
153
 
154
   The REDUCE flag is true if you want the cycles reduced to single
155
   nodes.  Only consider nodes that have the output bit set. */
156
 
157
int
158
ipa_utils_reduced_inorder (struct cgraph_node **order,
159
                           bool reduce, bool allow_overwritable,
160
                           bool (*ignore_edge) (struct cgraph_edge *))
161
{
162
  struct cgraph_node *node;
163
  struct searchc_env env;
164
  splay_tree_node result;
165
  env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
166
  env.stack_size = 0;
167
  env.result = order;
168
  env.order_pos = 0;
169
  env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
170
  env.count = 1;
171
  env.reduce = reduce;
172
 
173
  for (node = cgraph_nodes; node; node = node->next)
174
    {
175
      enum availability avail = cgraph_function_body_availability (node);
176
 
177
      if (avail > AVAIL_OVERWRITABLE
178
          || (allow_overwritable
179
              && (avail == AVAIL_OVERWRITABLE)))
180
        {
181
          /* Reuse the info if it is already there.  */
182
          struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
183
          if (!info)
184
            info = XCNEW (struct ipa_dfs_info);
185
          info->new_node = true;
186
          info->on_stack = false;
187
          info->next_cycle = NULL;
188
          node->aux = info;
189
 
190
          splay_tree_insert (env.nodes_marked_new,
191
                             (splay_tree_key)node->uid,
192
                             (splay_tree_value)node);
193
        }
194
      else
195
        node->aux = NULL;
196
    }
197
  result = splay_tree_min (env.nodes_marked_new);
198
  while (result)
199
    {
200
      node = (struct cgraph_node *)result->value;
201
      searchc (&env, node, ignore_edge);
202
      result = splay_tree_min (env.nodes_marked_new);
203
    }
204
  splay_tree_delete (env.nodes_marked_new);
205
  free (env.stack);
206
 
207
  return env.order_pos;
208
}
209
 
210
 
211
/* Given a memory reference T, will return the variable at the bottom
212
   of the access.  Unlike get_base_address, this will recurse thru
213
   INDIRECT_REFS.  */
214
 
215
tree
216
get_base_var (tree t)
217
{
218
  while (!SSA_VAR_P (t)
219
         && (!CONSTANT_CLASS_P (t))
220
         && TREE_CODE (t) != LABEL_DECL
221
         && TREE_CODE (t) != FUNCTION_DECL
222
         && TREE_CODE (t) != CONST_DECL
223
         && TREE_CODE (t) != CONSTRUCTOR)
224
    {
225
      t = TREE_OPERAND (t, 0);
226
    }
227
  return t;
228
}
229
 

powered by: WebSVN 2.1.0

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