1169689Skan/* Callgraph based analysis of static variables.
2169689Skan   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3169689Skan   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4169689Skan
5169689SkanThis file is part of GCC.
6169689Skan
7169689SkanGCC is free software; you can redistribute it and/or modify it under
8169689Skanthe terms of the GNU General Public License as published by the Free
9169689SkanSoftware Foundation; either version 2, or (at your option) any later
10169689Skanversion.
11169689Skan
12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY
13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or
14169689SkanFITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15169689Skanfor more details.
16169689Skan
17169689SkanYou should have received a copy of the GNU General Public License
18169689Skanalong with GCC; see the file COPYING.  If not, write to the Free
19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20169689Skan02110-1301, USA.  */
21169689Skan
22169689Skan/* This file mark functions as being either const (TREE_READONLY) or
23169689Skan   pure (DECL_IS_PURE).
24169689Skan
25169689Skan   This must be run after inlining decisions have been made since
26169689Skan   otherwise, the local sets will not contain information that is
27169689Skan   consistent with post inlined state.  The global sets are not prone
28169689Skan   to this problem since they are by definition transitive.  */
29169689Skan
30169689Skan/* The code in this module is called by the ipa pass manager. It
31169689Skan   should be one of the later passes since it's information is used by
32169689Skan   the rest of the compilation. */
33169689Skan
34169689Skan#include "config.h"
35169689Skan#include "system.h"
36169689Skan#include "coretypes.h"
37169689Skan#include "tm.h"
38169689Skan#include "tree.h"
39169689Skan#include "tree-flow.h"
40169689Skan#include "tree-inline.h"
41169689Skan#include "tree-pass.h"
42169689Skan#include "langhooks.h"
43169689Skan#include "pointer-set.h"
44169689Skan#include "ggc.h"
45169689Skan#include "ipa-utils.h"
46169689Skan#include "c-common.h"
47169689Skan#include "tree-gimple.h"
48169689Skan#include "cgraph.h"
49169689Skan#include "output.h"
50169689Skan#include "flags.h"
51169689Skan#include "timevar.h"
52169689Skan#include "diagnostic.h"
53169689Skan#include "langhooks.h"
54169689Skan#include "target.h"
55169689Skan
56169689Skanstatic struct pointer_set_t *visited_nodes;
57169689Skan
58169689Skan/* Lattice values for const and pure functions.  Everything starts out
59169689Skan   being const, then may drop to pure and then neither depending on
60169689Skan   what is found.  */
61169689Skanenum pure_const_state_e
62169689Skan{
63169689Skan  IPA_CONST,
64169689Skan  IPA_PURE,
65169689Skan  IPA_NEITHER
66169689Skan};
67169689Skan
68169689Skan/* Holder inserted into the ipa_dfs_info aux field to hold the
69169689Skan   const_state.  */
70169689Skanstruct funct_state_d
71169689Skan{
72169689Skan  enum pure_const_state_e pure_const_state;
73169689Skan  bool state_set_in_source;
74169689Skan};
75169689Skan
76169689Skantypedef struct funct_state_d * funct_state;
77169689Skan
78169689Skan/* Return the function state from NODE.  */
79169689Skan
80169689Skanstatic inline funct_state
81169689Skanget_function_state (struct cgraph_node *node)
82169689Skan{
83169689Skan  struct ipa_dfs_info * info = node->aux;
84169689Skan  return info->aux;
85169689Skan}
86169689Skan
87169689Skan/* Check to see if the use (or definition when CHECHING_WRITE is true)
88169689Skan   variable T is legal in a function that is either pure or const.  */
89169689Skan
90169689Skanstatic inline void
91169689Skancheck_decl (funct_state local,
92169689Skan	    tree t, bool checking_write)
93169689Skan{
94169689Skan  /* If the variable has the "used" attribute, treat it as if it had a
95169689Skan     been touched by the devil.  */
96169689Skan  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
97169689Skan    {
98169689Skan      local->pure_const_state = IPA_NEITHER;
99169689Skan      return;
100169689Skan    }
101169689Skan
102169689Skan  /* Do not want to do anything with volatile except mark any
103169689Skan     function that uses one to be not const or pure.  */
104169689Skan  if (TREE_THIS_VOLATILE (t))
105169689Skan    {
106169689Skan      local->pure_const_state = IPA_NEITHER;
107169689Skan      return;
108169689Skan    }
109169689Skan
110169689Skan  /* Do not care about a local automatic that is not static.  */
111169689Skan  if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
112169689Skan    return;
113169689Skan
114169689Skan  /* Since we have dealt with the locals and params cases above, if we
115169689Skan     are CHECKING_WRITE, this cannot be a pure or constant
116169689Skan     function.  */
117169689Skan  if (checking_write)
118169689Skan    local->pure_const_state = IPA_NEITHER;
119169689Skan
120169689Skan  if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
121169689Skan    {
122169689Skan      /* If the front end set the variable to be READONLY and
123169689Skan	 constant, we can allow this variable in pure or const
124169689Skan	 functions but the scope is too large for our analysis to set
125169689Skan	 these bits ourselves.  */
126169689Skan
127169689Skan      if (TREE_READONLY (t)
128169689Skan	  && DECL_INITIAL (t)
129169689Skan	  && is_gimple_min_invariant (DECL_INITIAL (t)))
130169689Skan	; /* Read of a constant, do not change the function state.  */
131169689Skan      else
132169689Skan	{
133169689Skan	  /* Just a regular read.  */
134169689Skan	  if (local->pure_const_state == IPA_CONST)
135169689Skan	    local->pure_const_state = IPA_PURE;
136169689Skan	}
137169689Skan    }
138169689Skan
139169689Skan  /* Compilation level statics can be read if they are readonly
140169689Skan     variables.  */
141169689Skan  if (TREE_READONLY (t))
142169689Skan    return;
143169689Skan
144169689Skan  /* Just a regular read.  */
145169689Skan  if (local->pure_const_state == IPA_CONST)
146169689Skan    local->pure_const_state = IPA_PURE;
147169689Skan}
148169689Skan
149169689Skan/* If T is a VAR_DECL check to see if it is an allowed reference.  */
150169689Skan
151169689Skanstatic void
152169689Skancheck_operand (funct_state local,
153169689Skan	       tree t, bool checking_write)
154169689Skan{
155169689Skan  if (!t) return;
156169689Skan
157169689Skan  if (TREE_CODE (t) == VAR_DECL)
158169689Skan    check_decl (local, t, checking_write);
159169689Skan}
160169689Skan
161169689Skan/* Examine tree T for references.  */
162169689Skan
163169689Skanstatic void
164169689Skancheck_tree (funct_state local, tree t, bool checking_write)
165169689Skan{
166169689Skan  if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
167169689Skan    return;
168169689Skan
169169689Skan  /* Any tree which is volatile disqualifies thie function from being
170169689Skan     const or pure. */
171169689Skan  if (TREE_THIS_VOLATILE (t))
172169689Skan    {
173169689Skan      local->pure_const_state = IPA_NEITHER;
174169689Skan      return;
175169689Skan    }
176169689Skan
177169689Skan  while (TREE_CODE (t) == REALPART_EXPR
178169689Skan	 || TREE_CODE (t) == IMAGPART_EXPR
179169689Skan	 || handled_component_p (t))
180169689Skan    {
181169689Skan      if (TREE_CODE (t) == ARRAY_REF)
182169689Skan	check_operand (local, TREE_OPERAND (t, 1), false);
183169689Skan      t = TREE_OPERAND (t, 0);
184169689Skan    }
185169689Skan
186169689Skan  /* The bottom of an indirect reference can only be read, not
187169689Skan     written.  */
188169689Skan  if (INDIRECT_REF_P (t))
189169689Skan    {
190169689Skan      check_tree (local, TREE_OPERAND (t, 0), false);
191169689Skan
192169689Skan      /* Any indirect reference that occurs on the lhs
193169689Skan	 disqualifies the function from being pure or const. Any
194169689Skan	 indirect reference that occurs on the rhs disqualifies the
195169689Skan	 function from being const.  */
196169689Skan      if (checking_write)
197169689Skan	{
198169689Skan	  local->pure_const_state = IPA_NEITHER;
199169689Skan	  return;
200169689Skan	}
201169689Skan      else if (local->pure_const_state == IPA_CONST)
202169689Skan	local->pure_const_state = IPA_PURE;
203169689Skan    }
204169689Skan
205169689Skan  if (SSA_VAR_P (t))
206169689Skan    check_operand (local, t, checking_write);
207169689Skan}
208169689Skan
209169689Skan/* Scan tree T to see if there are any addresses taken in within T.  */
210169689Skan
211169689Skanstatic void
212169689Skanlook_for_address_of (funct_state local, tree t)
213169689Skan{
214169689Skan  if (TREE_CODE (t) == ADDR_EXPR)
215169689Skan    {
216169689Skan      tree x = get_base_var (t);
217169689Skan      if (TREE_CODE (x) == VAR_DECL)
218169689Skan	{
219169689Skan	  check_decl (local, x, false);
220169689Skan
221169689Skan	  /* Taking the address of something appears to be reasonable
222169689Skan	     in PURE code.  Not allowed in const.  */
223169689Skan	  if (local->pure_const_state == IPA_CONST)
224169689Skan	    local->pure_const_state = IPA_PURE;
225169689Skan	}
226169689Skan    }
227169689Skan}
228169689Skan
229169689Skan/* Check to see if T is a read or address of operation on a var we are
230169689Skan   interested in analyzing.  LOCAL is passed in to get access to its
231169689Skan   bit vectors.  */
232169689Skan
233169689Skanstatic void
234169689Skancheck_rhs_var (funct_state local, tree t)
235169689Skan{
236169689Skan  look_for_address_of (local, t);
237169689Skan
238169689Skan  /* Memcmp and strlen can both trap and they are declared pure.  */
239169689Skan  if (tree_could_trap_p (t)
240169689Skan      && local->pure_const_state == IPA_CONST)
241169689Skan    local->pure_const_state = IPA_PURE;
242169689Skan
243169689Skan  check_tree(local, t, false);
244169689Skan}
245169689Skan
246169689Skan/* Check to see if T is an assignment to a var we are interested in
247169689Skan   analyzing.  LOCAL is passed in to get access to its bit vectors. */
248169689Skan
249169689Skanstatic void
250169689Skancheck_lhs_var (funct_state local, tree t)
251169689Skan{
252169689Skan  /* Memcmp and strlen can both trap and they are declared pure.
253169689Skan     Which seems to imply that we can apply the same rule here.  */
254169689Skan  if (tree_could_trap_p (t)
255169689Skan      && local->pure_const_state == IPA_CONST)
256169689Skan    local->pure_const_state = IPA_PURE;
257169689Skan
258169689Skan  check_tree(local, t, true);
259169689Skan}
260169689Skan
261169689Skan/* This is a scaled down version of get_asm_expr_operands from
262169689Skan   tree_ssa_operands.c.  The version there runs much later and assumes
263169689Skan   that aliasing information is already available. Here we are just
264169689Skan   trying to find if the set of inputs and outputs contain references
265169689Skan   or address of operations to local static variables.  STMT is the
266169689Skan   actual asm statement.  */
267169689Skan
268169689Skanstatic void
269169689Skanget_asm_expr_operands (funct_state local, tree stmt)
270169689Skan{
271169689Skan  int noutputs = list_length (ASM_OUTPUTS (stmt));
272169689Skan  const char **oconstraints
273169689Skan    = (const char **) alloca ((noutputs) * sizeof (const char *));
274169689Skan  int i;
275169689Skan  tree link;
276169689Skan  const char *constraint;
277169689Skan  bool allows_mem, allows_reg, is_inout;
278169689Skan
279169689Skan  for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
280169689Skan    {
281169689Skan      oconstraints[i] = constraint
282169689Skan	= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
283169689Skan      parse_output_constraint (&constraint, i, 0, 0,
284169689Skan			       &allows_mem, &allows_reg, &is_inout);
285169689Skan
286169689Skan      check_lhs_var (local, TREE_VALUE (link));
287169689Skan    }
288169689Skan
289169689Skan  for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
290169689Skan    {
291169689Skan      constraint
292169689Skan	= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
293169689Skan      parse_input_constraint (&constraint, 0, 0, noutputs, 0,
294169689Skan			      oconstraints, &allows_mem, &allows_reg);
295169689Skan
296169689Skan      check_rhs_var (local, TREE_VALUE (link));
297169689Skan    }
298169689Skan
299169689Skan  for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
300169689Skan    if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1)
301169689Skan      /* Abandon all hope, ye who enter here. */
302169689Skan      local->pure_const_state = IPA_NEITHER;
303169689Skan
304169689Skan  if (ASM_VOLATILE_P (stmt))
305169689Skan    local->pure_const_state = IPA_NEITHER;
306169689Skan}
307169689Skan
308169689Skan/* Check the parameters of a function call to CALL_EXPR to see if
309169689Skan   there are any references in the parameters that are not allowed for
310169689Skan   pure or const functions.  Also check to see if this is either an
311169689Skan   indirect call, a call outside the compilation unit, or has special
312169689Skan   attributes that may also effect the purity.  The CALL_EXPR node for
313169689Skan   the entire call expression.  */
314169689Skan
315169689Skanstatic void
316169689Skancheck_call (funct_state local, tree call_expr)
317169689Skan{
318169689Skan  int flags = call_expr_flags(call_expr);
319169689Skan  tree operand_list = TREE_OPERAND (call_expr, 1);
320169689Skan  tree operand;
321169689Skan  tree callee_t = get_callee_fndecl (call_expr);
322169689Skan  struct cgraph_node* callee;
323169689Skan  enum availability avail = AVAIL_NOT_AVAILABLE;
324169689Skan
325169689Skan  for (operand = operand_list;
326169689Skan       operand != NULL_TREE;
327169689Skan       operand = TREE_CHAIN (operand))
328169689Skan    {
329169689Skan      tree argument = TREE_VALUE (operand);
330169689Skan      check_rhs_var (local, argument);
331169689Skan    }
332169689Skan
333169689Skan  /* The const and pure flags are set by a variety of places in the
334169689Skan     compiler (including here).  If someone has already set the flags
335169689Skan     for the callee, (such as for some of the builtins) we will use
336169689Skan     them, otherwise we will compute our own information.
337169689Skan
338169689Skan     Const and pure functions have less clobber effects than other
339169689Skan     functions so we process these first.  Otherwise if it is a call
340169689Skan     outside the compilation unit or an indirect call we punt.  This
341169689Skan     leaves local calls which will be processed by following the call
342169689Skan     graph.  */
343169689Skan  if (callee_t)
344169689Skan    {
345169689Skan      callee = cgraph_node(callee_t);
346169689Skan      avail = cgraph_function_body_availability (callee);
347169689Skan
348169689Skan      /* When bad things happen to bad functions, they cannot be const
349169689Skan	 or pure.  */
350169689Skan      if (setjmp_call_p (callee_t))
351169689Skan	local->pure_const_state = IPA_NEITHER;
352169689Skan
353169689Skan      if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
354169689Skan	switch (DECL_FUNCTION_CODE (callee_t))
355169689Skan	  {
356169689Skan	  case BUILT_IN_LONGJMP:
357169689Skan	  case BUILT_IN_NONLOCAL_GOTO:
358169689Skan	    local->pure_const_state = IPA_NEITHER;
359169689Skan	    break;
360169689Skan	  default:
361169689Skan	    break;
362169689Skan	  }
363169689Skan    }
364169689Skan
365169689Skan  /* The callee is either unknown (indirect call) or there is just no
366169689Skan     scannable code for it (external call) .  We look to see if there
367169689Skan     are any bits available for the callee (such as by declaration or
368169689Skan     because it is builtin) and process solely on the basis of those
369169689Skan     bits. */
370169689Skan  if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
371169689Skan    {
372169689Skan      if (flags & ECF_PURE)
373169689Skan	{
374169689Skan	  if (local->pure_const_state == IPA_CONST)
375169689Skan	    local->pure_const_state = IPA_PURE;
376169689Skan	}
377169689Skan      else
378169689Skan	local->pure_const_state = IPA_NEITHER;
379169689Skan    }
380169689Skan  else
381169689Skan    {
382169689Skan      /* We have the code and we will scan it for the effects. */
383169689Skan      if (flags & ECF_PURE)
384169689Skan	{
385169689Skan	  if (local->pure_const_state == IPA_CONST)
386169689Skan	    local->pure_const_state = IPA_PURE;
387169689Skan	}
388169689Skan    }
389169689Skan}
390169689Skan
391169689Skan/* TP is the part of the tree currently under the microscope.
392169689Skan   WALK_SUBTREES is part of the walk_tree api but is unused here.
393169689Skan   DATA is cgraph_node of the function being walked.  */
394169689Skan
395169689Skan/* FIXME: When this is converted to run over SSA form, this code
396169689Skan   should be converted to use the operand scanner.  */
397169689Skan
398169689Skanstatic tree
399169689Skanscan_function (tree *tp,
400169689Skan		      int *walk_subtrees,
401169689Skan		      void *data)
402169689Skan{
403169689Skan  struct cgraph_node *fn = data;
404169689Skan  tree t = *tp;
405169689Skan  funct_state local = get_function_state (fn);
406169689Skan
407169689Skan  switch (TREE_CODE (t))
408169689Skan    {
409169689Skan    case VAR_DECL:
410169689Skan      if (DECL_INITIAL (t))
411169689Skan	walk_tree (&DECL_INITIAL (t), scan_function, fn, visited_nodes);
412169689Skan      *walk_subtrees = 0;
413169689Skan      break;
414169689Skan
415169689Skan    case MODIFY_EXPR:
416169689Skan      {
417169689Skan	/* First look on the lhs and see what variable is stored to */
418169689Skan	tree lhs = TREE_OPERAND (t, 0);
419169689Skan	tree rhs = TREE_OPERAND (t, 1);
420169689Skan	check_lhs_var (local, lhs);
421169689Skan
422169689Skan	/* For the purposes of figuring out what the cast affects */
423169689Skan
424169689Skan	/* Next check the operands on the rhs to see if they are ok. */
425169689Skan	switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
426169689Skan	  {
427169689Skan	  case tcc_binary:
428169689Skan 	    {
429169689Skan 	      tree op0 = TREE_OPERAND (rhs, 0);
430169689Skan 	      tree op1 = TREE_OPERAND (rhs, 1);
431169689Skan 	      check_rhs_var (local, op0);
432169689Skan 	      check_rhs_var (local, op1);
433169689Skan	    }
434169689Skan	    break;
435169689Skan	  case tcc_unary:
436169689Skan 	    {
437169689Skan 	      tree op0 = TREE_OPERAND (rhs, 0);
438169689Skan 	      check_rhs_var (local, op0);
439169689Skan 	    }
440169689Skan
441169689Skan	    break;
442169689Skan	  case tcc_reference:
443169689Skan	    check_rhs_var (local, rhs);
444169689Skan	    break;
445169689Skan	  case tcc_declaration:
446169689Skan	    check_rhs_var (local, rhs);
447169689Skan	    break;
448169689Skan	  case tcc_expression:
449169689Skan	    switch (TREE_CODE (rhs))
450169689Skan	      {
451169689Skan	      case ADDR_EXPR:
452169689Skan		check_rhs_var (local, rhs);
453169689Skan		break;
454169689Skan	      case CALL_EXPR:
455169689Skan		check_call (local, rhs);
456169689Skan		break;
457169689Skan	      default:
458169689Skan		break;
459169689Skan	      }
460169689Skan	    break;
461169689Skan	  default:
462169689Skan	    break;
463169689Skan	  }
464169689Skan	*walk_subtrees = 0;
465169689Skan      }
466169689Skan      break;
467169689Skan
468169689Skan    case ADDR_EXPR:
469169689Skan      /* This case is here to find addresses on rhs of constructors in
470169689Skan	 decl_initial of static variables. */
471169689Skan      check_rhs_var (local, t);
472169689Skan      *walk_subtrees = 0;
473169689Skan      break;
474169689Skan
475169689Skan    case LABEL_EXPR:
476169689Skan      if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
477169689Skan	/* Target of long jump. */
478169689Skan	local->pure_const_state = IPA_NEITHER;
479169689Skan      break;
480169689Skan
481169689Skan    case CALL_EXPR:
482169689Skan      check_call (local, t);
483169689Skan      *walk_subtrees = 0;
484169689Skan      break;
485169689Skan
486169689Skan    case ASM_EXPR:
487169689Skan      get_asm_expr_operands (local, t);
488169689Skan      *walk_subtrees = 0;
489169689Skan      break;
490169689Skan
491169689Skan    default:
492169689Skan      break;
493169689Skan    }
494169689Skan  return NULL;
495169689Skan}
496169689Skan
497169689Skan/* This is the main routine for finding the reference patterns for
498169689Skan   global variables within a function FN.  */
499169689Skan
500169689Skanstatic void
501169689Skananalyze_function (struct cgraph_node *fn)
502169689Skan{
503169689Skan  funct_state l = XCNEW (struct funct_state_d);
504169689Skan  tree decl = fn->decl;
505169689Skan  struct ipa_dfs_info * w_info = fn->aux;
506169689Skan
507169689Skan  w_info->aux = l;
508169689Skan
509169689Skan  l->pure_const_state = IPA_CONST;
510169689Skan  l->state_set_in_source = false;
511169689Skan
512169689Skan  /* If this function does not return normally or does not bind local,
513169689Skan     do not touch this unless it has been marked as const or pure by the
514169689Skan     front end.  */
515169689Skan  if (TREE_THIS_VOLATILE (decl)
516169689Skan      || !targetm.binds_local_p (decl))
517169689Skan    {
518169689Skan      l->pure_const_state = IPA_NEITHER;
519169689Skan      return;
520169689Skan    }
521169689Skan
522169689Skan  if (TREE_READONLY (decl))
523169689Skan    {
524169689Skan      l->pure_const_state = IPA_CONST;
525169689Skan      l->state_set_in_source = true;
526169689Skan    }
527169689Skan  if (DECL_IS_PURE (decl))
528169689Skan    {
529169689Skan      l->pure_const_state = IPA_PURE;
530169689Skan      l->state_set_in_source = true;
531169689Skan    }
532169689Skan
533169689Skan  if (dump_file)
534169689Skan    {
535169689Skan      fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ",
536169689Skan	       cgraph_node_name (fn),
537169689Skan	       l->pure_const_state);
538169689Skan    }
539169689Skan
540169689Skan  if (!l->state_set_in_source)
541169689Skan    {
542169689Skan      struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
543169689Skan      basic_block this_block;
544169689Skan
545169689Skan      FOR_EACH_BB_FN (this_block, this_cfun)
546169689Skan	{
547169689Skan	  block_stmt_iterator bsi;
548169689Skan	  for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
549169689Skan	    {
550169689Skan	      walk_tree (bsi_stmt_ptr (bsi), scan_function,
551169689Skan			 fn, visited_nodes);
552169689Skan	      if (l->pure_const_state == IPA_NEITHER)
553169689Skan		goto end;
554169689Skan	    }
555169689Skan	}
556169689Skan
557169689Skan      if (l->pure_const_state != IPA_NEITHER)
558169689Skan	{
559169689Skan	  tree old_decl = current_function_decl;
560169689Skan	  /* Const functions cannot have back edges (an
561169689Skan	     indication of possible infinite loop side
562169689Skan	     effect.  */
563169689Skan
564169689Skan	  current_function_decl = fn->decl;
565169689Skan
566169689Skan	  /* The C++ front end, has a tendency to some times jerk away
567169689Skan	     a function after it has created it.  This should have
568169689Skan	     been fixed.  */
569169689Skan	  gcc_assert (DECL_STRUCT_FUNCTION (fn->decl));
570169689Skan
571169689Skan	  push_cfun (DECL_STRUCT_FUNCTION (fn->decl));
572169689Skan
573169689Skan	  if (mark_dfs_back_edges ())
574169689Skan	    l->pure_const_state = IPA_NEITHER;
575169689Skan
576169689Skan	  current_function_decl = old_decl;
577169689Skan	  pop_cfun ();
578169689Skan	}
579169689Skan    }
580169689Skan
581169689Skanend:
582169689Skan  if (dump_file)
583169689Skan    {
584169689Skan      fprintf (dump_file, "after local analysis of %s with initial value = %d\n ",
585169689Skan	       cgraph_node_name (fn),
586169689Skan	       l->pure_const_state);
587169689Skan    }
588169689Skan}
589169689Skan
590169689Skan
591169689Skan/* Produce the global information by preforming a transitive closure
592169689Skan   on the local information that was produced by ipa_analyze_function
593169689Skan   and ipa_analyze_variable.  */
594169689Skan
595169689Skanstatic unsigned int
596169689Skanstatic_execute (void)
597169689Skan{
598169689Skan  struct cgraph_node *node;
599169689Skan  struct cgraph_node *w;
600169689Skan  struct cgraph_node **order =
601169689Skan    XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
602169689Skan  int order_pos = order_pos = ipa_utils_reduced_inorder (order, true, false);
603169689Skan  int i;
604169689Skan  struct ipa_dfs_info * w_info;
605169689Skan
606169689Skan  if (!memory_identifier_string)
607169689Skan    memory_identifier_string = build_string(7, "memory");
608169689Skan
609169689Skan  /* There are some shared nodes, in particular the initializers on
610169689Skan     static declarations.  We do not need to scan them more than once
611169689Skan     since all we would be interested in are the addressof
612169689Skan     operations.  */
613169689Skan  visited_nodes = pointer_set_create ();
614169689Skan
615169689Skan  /* Process all of the functions.
616169689Skan
617169689Skan     We do not want to process any of the clones so we check that this
618169689Skan     is a master clone.  However, we do NOT process any
619169689Skan     AVAIL_OVERWRITABLE functions (these are never clones) we cannot
620169689Skan     guarantee that what we learn about the one we see will be true
621169689Skan     for the one that overriders it.
622169689Skan  */
623169689Skan  for (node = cgraph_nodes; node; node = node->next)
624169689Skan    if (node->analyzed && cgraph_is_master_clone (node))
625169689Skan      analyze_function (node);
626169689Skan
627169689Skan  pointer_set_destroy (visited_nodes);
628169689Skan  visited_nodes = NULL;
629169689Skan  if (dump_file)
630169689Skan    {
631169689Skan      dump_cgraph (dump_file);
632169689Skan      ipa_utils_print_order(dump_file, "reduced", order, order_pos);
633169689Skan    }
634169689Skan
635169689Skan  /* Propagate the local information thru the call graph to produce
636169689Skan     the global information.  All the nodes within a cycle will have
637169689Skan     the same info so we collapse cycles first.  Then we can do the
638169689Skan     propagation in one pass from the leaves to the roots.  */
639169689Skan  for (i = 0; i < order_pos; i++ )
640169689Skan    {
641169689Skan      enum pure_const_state_e pure_const_state = IPA_CONST;
642235623Spfg      int count = 0;
643169689Skan      node = order[i];
644169689Skan
645169689Skan      /* Find the worst state for any node in the cycle.  */
646169689Skan      w = node;
647169689Skan      while (w)
648169689Skan	{
649169689Skan	  funct_state w_l = get_function_state (w);
650169689Skan	  if (pure_const_state < w_l->pure_const_state)
651169689Skan	    pure_const_state = w_l->pure_const_state;
652169689Skan
653169689Skan	  if (pure_const_state == IPA_NEITHER)
654169689Skan	    break;
655169689Skan
656169689Skan	  if (!w_l->state_set_in_source)
657169689Skan	    {
658169689Skan	      struct cgraph_edge *e;
659235623Spfg	      count++;
660235623Spfg
661235623Spfg	      /* FIXME!!!  Because of pr33826, we cannot have either
662235623Spfg		 immediate or transitive recursive functions marked as
663235623Spfg		 pure or const because dce can delete a function that
664235623Spfg		 is in reality an infinite loop.  A better solution
665235623Spfg		 than just outlawing them is to add another bit the
666235623Spfg		 functions to distinguish recursive from non recursive
667235623Spfg		 pure and const function.  This would allow the
668235623Spfg		 recursive ones to be cse'd but not dce'd.  In this
669235623Spfg		 same vein, we could allow functions with loops to
670235623Spfg		 also be cse'd but not dce'd.
671235623Spfg
672235623Spfg		 Unfortunately we are late in stage 3, and the fix
673235623Spfg		 described above is is not appropriate.  */
674235623Spfg	      if (count > 1)
675235623Spfg		{
676235623Spfg		  pure_const_state = IPA_NEITHER;
677235623Spfg		  break;
678235623Spfg		}
679235623Spfg
680169689Skan	      for (e = w->callees; e; e = e->next_callee)
681169689Skan		{
682169689Skan		  struct cgraph_node *y = e->callee;
683169689Skan		  /* Only look at the master nodes and skip external nodes.  */
684169689Skan		  y = cgraph_master_clone (y);
685235623Spfg
686235623Spfg		  /* Check for immediate recursive functions.  See the
687235623Spfg		     FIXME above.  */
688235623Spfg		  if (w == y)
689235623Spfg		    {
690235623Spfg		      pure_const_state = IPA_NEITHER;
691235623Spfg		      break;
692235623Spfg		    }
693169689Skan		  if (y)
694169689Skan		    {
695169689Skan		      funct_state y_l = get_function_state (y);
696169689Skan		      if (pure_const_state < y_l->pure_const_state)
697169689Skan			pure_const_state = y_l->pure_const_state;
698169689Skan		      if (pure_const_state == IPA_NEITHER)
699169689Skan			break;
700169689Skan		    }
701169689Skan		}
702169689Skan	    }
703169689Skan	  w_info = w->aux;
704169689Skan	  w = w_info->next_cycle;
705169689Skan	}
706169689Skan
707169689Skan      /* Copy back the region's pure_const_state which is shared by
708169689Skan	 all nodes in the region.  */
709169689Skan      w = node;
710169689Skan      while (w)
711169689Skan	{
712169689Skan	  funct_state w_l = get_function_state (w);
713169689Skan
714169689Skan	  /* All nodes within a cycle share the same info.  */
715169689Skan	  if (!w_l->state_set_in_source)
716169689Skan	    {
717169689Skan	      w_l->pure_const_state = pure_const_state;
718169689Skan	      switch (pure_const_state)
719169689Skan		{
720169689Skan		case IPA_CONST:
721169689Skan		  TREE_READONLY (w->decl) = 1;
722169689Skan		  if (dump_file)
723169689Skan		    fprintf (dump_file, "Function found to be const: %s\n",
724169689Skan			     lang_hooks.decl_printable_name(w->decl, 2));
725169689Skan		  break;
726169689Skan
727169689Skan		case IPA_PURE:
728169689Skan		  DECL_IS_PURE (w->decl) = 1;
729169689Skan		  if (dump_file)
730169689Skan		    fprintf (dump_file, "Function found to be pure: %s\n",
731169689Skan			     lang_hooks.decl_printable_name(w->decl, 2));
732169689Skan		  break;
733169689Skan
734169689Skan		default:
735169689Skan		  break;
736169689Skan		}
737169689Skan	    }
738169689Skan	  w_info = w->aux;
739169689Skan	  w = w_info->next_cycle;
740169689Skan	}
741169689Skan    }
742169689Skan
743169689Skan  /* Cleanup. */
744169689Skan  for (node = cgraph_nodes; node; node = node->next)
745169689Skan    /* Get rid of the aux information.  */
746169689Skan    if (node->aux)
747169689Skan      {
748169689Skan	w_info = node->aux;
749169689Skan	if (w_info->aux)
750169689Skan	  free (w_info->aux);
751169689Skan	free (node->aux);
752169689Skan	node->aux = NULL;
753169689Skan      }
754169689Skan
755169689Skan  free (order);
756169689Skan  return 0;
757169689Skan}
758169689Skan
759169689Skanstatic bool
760169689Skangate_pure_const (void)
761169689Skan{
762169689Skan  return (flag_unit_at_a_time != 0 && flag_ipa_pure_const
763169689Skan	  /* Don't bother doing anything if the program has errors.  */
764169689Skan	  && !(errorcount || sorrycount));
765169689Skan}
766169689Skan
767169689Skanstruct tree_opt_pass pass_ipa_pure_const =
768169689Skan{
769169689Skan  "pure-const",		                /* name */
770169689Skan  gate_pure_const,			/* gate */
771169689Skan  static_execute,			/* execute */
772169689Skan  NULL,					/* sub */
773169689Skan  NULL,					/* next */
774169689Skan  0,					/* static_pass_number */
775169689Skan  TV_IPA_PURE_CONST,		        /* tv_id */
776169689Skan  0,	                                /* properties_required */
777169689Skan  0,					/* properties_provided */
778169689Skan  0,					/* properties_destroyed */
779169689Skan  0,					/* todo_flags_start */
780169689Skan  0,                                    /* todo_flags_finish */
781169689Skan  0					/* letter */
782169689Skan};
783169689Skan
784169689Skan
785