[gcc.git] / gcc / tree-iterator.c

/* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod  <amacleod@redhat.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING.  If not, write to
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "tree-gimple.h"
#include "tree-iterator.h"
#include "ggc.h"


/* This is a cache of STATEMENT_LIST nodes.  We create and destroy them
   fairly often during gimplification.  */

static GTY ((deletable (""))) tree stmt_list_cache;

tree
alloc_stmt_list (void)
{
  tree list = stmt_list_cache;
  if (list)
    {
      stmt_list_cache = TREE_CHAIN (list);
      gcc_assert (stmt_list_cache != list);
      memset (list, 0, sizeof(struct tree_common));
      TREE_SET_CODE (list, STATEMENT_LIST);
    }
  else
    list = make_node (STATEMENT_LIST);
  TREE_TYPE (list) = void_type_node;
  return list;
}

void
free_stmt_list (tree t)
{
  gcc_assert (!STATEMENT_LIST_HEAD (t));
  gcc_assert (!STATEMENT_LIST_TAIL (t));
  /* If this triggers, it's a sign that the same list is being freed
     twice.  */
  gcc_assert (t != stmt_list_cache || stmt_list_cache == NULL);
  TREE_CHAIN (t) = stmt_list_cache;
  stmt_list_cache = t;
}

/* Links a statement, or a chain of statements, before the current stmt.  */

void
tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
{
  struct tree_statement_list_node *head, *tail, *cur;

  /* Die on looping.  */
  gcc_assert (t != i->container);

  if (TREE_CODE (t) == STATEMENT_LIST)
    {
      head = STATEMENT_LIST_HEAD (t);
      tail = STATEMENT_LIST_TAIL (t);
      STATEMENT_LIST_HEAD (t) = NULL;
      STATEMENT_LIST_TAIL (t) = NULL;

      free_stmt_list (t);

      /* Empty statement lists need no work.  */
      if (!head || !tail)
	{
	  gcc_assert (head == tail);
	  return;
	}
    }
  else
    {
      head = ggc_alloc (sizeof (*head));
      head->prev = NULL;
      head->next = NULL;
      head->stmt = t;
      tail = head;
    }

  TREE_SIDE_EFFECTS (i->container) = 1;

  cur = i->ptr;

  /* Link it into the list.  */
  if (cur)
    {
      head->prev = cur->prev;
      if (head->prev)
	head->prev->next = head;
      else
	STATEMENT_LIST_HEAD (i->container) = head;
      tail->next = cur;
      cur->prev = tail;
    }
  else
    {
      head->prev = STATEMENT_LIST_TAIL (i->container);
      if (head->prev)
       head->prev->next = head;
      else
       STATEMENT_LIST_HEAD (i->container) = head;
      STATEMENT_LIST_TAIL (i->container) = tail;
    }

  /* Update the iterator, if requested.  */
  switch (mode)
    {
    case TSI_NEW_STMT:
    case TSI_CONTINUE_LINKING:
    case TSI_CHAIN_START:
      i->ptr = head;
      break;
    case TSI_CHAIN_END:
      i->ptr = tail;
      break;
    case TSI_SAME_STMT:
      break;
    }
}

/* Links a statement, or a chain of statements, after the current stmt.  */

void
tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
{
  struct tree_statement_list_node *head, *tail, *cur;

  /* Die on looping.  */
  gcc_assert (t != i->container);

  if (TREE_CODE (t) == STATEMENT_LIST)
    {
      head = STATEMENT_LIST_HEAD (t);
      tail = STATEMENT_LIST_TAIL (t);
      STATEMENT_LIST_HEAD (t) = NULL;
      STATEMENT_LIST_TAIL (t) = NULL;

      free_stmt_list (t);

      /* Empty statement lists need no work.  */
      if (!head || !tail)
	{
	  gcc_assert (head == tail);
	  return;
	}
    }
  else
    {
      head = ggc_alloc (sizeof (*head));
      head->prev = NULL;
      head->next = NULL;
      head->stmt = t;
      tail = head;
    }

  TREE_SIDE_EFFECTS (i->container) = 1;

  cur = i->ptr;

  /* Link it into the list.  */
  if (cur)
    {
      tail->next = cur->next;
      if (tail->next)
	tail->next->prev = tail;
      else
	STATEMENT_LIST_TAIL (i->container) = tail;
      head->prev = cur;
      cur->next = head;
    }
  else
    {
      gcc_assert (!STATEMENT_LIST_TAIL (i->container));
      STATEMENT_LIST_HEAD (i->container) = head;
      STATEMENT_LIST_TAIL (i->container) = tail;
    }

  /* Update the iterator, if requested.  */
  switch (mode)
    {
    case TSI_NEW_STMT:
    case TSI_CHAIN_START:
      i->ptr = head;
      break;
    case TSI_CONTINUE_LINKING:
    case TSI_CHAIN_END:
      i->ptr = tail;
      break;
    case TSI_SAME_STMT:
      gcc_assert (cur);
      break;
    }
}

/* Remove a stmt from the tree list.  The iterator is updated to point to
   the next stmt.  */

void
tsi_delink (tree_stmt_iterator *i)
{
  struct tree_statement_list_node *cur, *next, *prev;

  cur = i->ptr;
  next = cur->next;
  prev = cur->prev;

  if (prev)
    prev->next = next;
  else
    STATEMENT_LIST_HEAD (i->container) = next;
  if (next)
    next->prev = prev;
  else
    STATEMENT_LIST_TAIL (i->container) = prev;

  if (!next && !prev)
    TREE_SIDE_EFFECTS (i->container) = 0;

  i->ptr = next;
}

/* Move all statements in the statement list after I to a new
   statement list.  I itself is unchanged.  */

tree
tsi_split_statement_list_after (const tree_stmt_iterator *i)
{
  struct tree_statement_list_node *cur, *next;
  tree old_sl, new_sl;

  cur = i->ptr;
  /* How can we possibly split after the end, or before the beginning?  */
  gcc_assert (cur);
  next = cur->next;

  old_sl = i->container;
  new_sl = alloc_stmt_list ();
  TREE_SIDE_EFFECTS (new_sl) = 1;

  STATEMENT_LIST_HEAD (new_sl) = next;
  STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
  STATEMENT_LIST_TAIL (old_sl) = cur;
  cur->next = NULL;
  next->prev = NULL;

  return new_sl;
}

/* Move all statements in the statement list before I to a new
   statement list.  I is set to the head of the new list.  */

tree
tsi_split_statement_list_before (tree_stmt_iterator *i)
{
  struct tree_statement_list_node *cur, *prev;
  tree old_sl, new_sl;

  cur = i->ptr;
  /* How can we possibly split after the end, or before the beginning?  */
  gcc_assert (cur);
  prev = cur->prev;

  old_sl = i->container;
  new_sl = alloc_stmt_list ();
  TREE_SIDE_EFFECTS (new_sl) = 1;
  i->container = new_sl;

  STATEMENT_LIST_HEAD (new_sl) = cur;
  STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
  STATEMENT_LIST_TAIL (old_sl) = prev;
  cur->prev = NULL;
  if (prev)
    prev->next = NULL;

  return new_sl;
}

/* Return the first expression in a sequence of COMPOUND_EXPRs,
   or in a STATEMENT_LIST.  */

tree
expr_first (tree expr)
{
  if (expr == NULL_TREE)
    return expr;

  if (TREE_CODE (expr) == STATEMENT_LIST)
    {
      struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
      return n ? n->stmt : NULL_TREE;
    }

  while (TREE_CODE (expr) == COMPOUND_EXPR)
    expr = TREE_OPERAND (expr, 0);
  return expr;
}

/* Return the last expression in a sequence of COMPOUND_EXPRs,
   or in a STATEMENT_LIST.  */

tree
expr_last (tree expr)
{
  if (expr == NULL_TREE)
    return expr;

  if (TREE_CODE (expr) == STATEMENT_LIST)
    {
      struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
      return n ? n->stmt : NULL_TREE;
    }

  while (TREE_CODE (expr) == COMPOUND_EXPR)
    expr = TREE_OPERAND (expr, 1);
  return expr;
}

/* If EXPR is a single statement return it.  If EXPR is a
   STATEMENT_LIST containing exactly one statement S, return S.
   Otherwise, return NULL.  */

tree 
expr_only (tree expr)
{
  if (expr == NULL_TREE)
    return NULL_TREE;

  if (TREE_CODE (expr) == STATEMENT_LIST)
    {
      struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
      if (n && STATEMENT_LIST_HEAD (expr) == n)
	return n->stmt;
      else
	return NULL_TREE;
    }

  if (TREE_CODE (expr) == COMPOUND_EXPR)
    return NULL_TREE;

  return expr;
}

#include "gt-tree-iterator.h"
Commit	Line	Data
6de9cd9a DN	1	/* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
	2	Copyright (C) 2003, 2004 Free Software Foundation, Inc.
	3	Contributed by Andrew MacLeod <amacleod@redhat.com>
	4
	5	This file is part of GCC.
	6
	7	GCC is free software; you can redistribute it and/or modify
	8	it under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 2, or (at your option)
	10	any later version.
	11
	12	GCC is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with GCC; see the file COPYING. If not, write to
366ccddb KC	19	the Free Software Foundation, 51 Franklin Street, Fifth Floor,
366ccddb KC	20	Boston, MA 02110-1301, USA. */
6de9cd9a DN	21
	22	#include "config.h"
	23	#include "system.h"
	24	#include "coretypes.h"
	25	#include "tree.h"
eadf906f	26	#include "tree-gimple.h"
6de9cd9a DN	27	#include "tree-iterator.h"
	28	#include "ggc.h"
	29
	30
	31	/* This is a cache of STATEMENT_LIST nodes. We create and destroy them
	32	fairly often during gimplification. */
	33
	34	static GTY ((deletable (""))) tree stmt_list_cache;
	35
	36	tree
	37	alloc_stmt_list (void)
	38	{
	39	tree list = stmt_list_cache;
	40	if (list)
	41	{
	42	stmt_list_cache = TREE_CHAIN (list);
50674e96	43	gcc_assert (stmt_list_cache != list);
325c3691 RH	44	memset (list, 0, sizeof(struct tree_common));
325c3691 RH	45	TREE_SET_CODE (list, STATEMENT_LIST);
6de9cd9a DN	46	}
6de9cd9a DN	47	else
325c3691 RH	48	list = make_node (STATEMENT_LIST);
325c3691 RH	49	TREE_TYPE (list) = void_type_node;
6de9cd9a DN	50	return list;
	51	}
	52
	53	void
	54	free_stmt_list (tree t)
	55	{
1e128c5f GB	56	gcc_assert (!STATEMENT_LIST_HEAD (t));
1e128c5f GB	57	gcc_assert (!STATEMENT_LIST_TAIL (t));
50674e96 DN	58	/* If this triggers, it's a sign that the same list is being freed
	59	twice. */
	60	gcc_assert (t != stmt_list_cache \|\| stmt_list_cache == NULL);
6de9cd9a DN	61	TREE_CHAIN (t) = stmt_list_cache;
	62	stmt_list_cache = t;
	63	}
	64
	65	/* Links a statement, or a chain of statements, before the current stmt. */
	66
	67	void
	68	tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
	69	{
	70	struct tree_statement_list_node head, tail, *cur;
	71
	72	/* Die on looping. */
1e128c5f	73	gcc_assert (t != i->container);
6de9cd9a	74
6de9cd9a DN	75	if (TREE_CODE (t) == STATEMENT_LIST)
	76	{
	77	head = STATEMENT_LIST_HEAD (t);
	78	tail = STATEMENT_LIST_TAIL (t);
	79	STATEMENT_LIST_HEAD (t) = NULL;
	80	STATEMENT_LIST_TAIL (t) = NULL;
	81
	82	free_stmt_list (t);
	83
	84	/* Empty statement lists need no work. */
	85	if (!head \|\| !tail)
	86	{
1e128c5f	87	gcc_assert (head == tail);
6de9cd9a DN	88	return;
	89	}
	90	}
	91	else
	92	{
	93	head = ggc_alloc (sizeof (*head));
	94	head->prev = NULL;
	95	head->next = NULL;
	96	head->stmt = t;
	97	tail = head;
	98	}
	99
325c3691 RH	100	TREE_SIDE_EFFECTS (i->container) = 1;
325c3691 RH	101
6de9cd9a DN	102	cur = i->ptr;
	103
	104	/* Link it into the list. */
	105	if (cur)
	106	{
	107	head->prev = cur->prev;
	108	if (head->prev)
	109	head->prev->next = head;
	110	else
	111	STATEMENT_LIST_HEAD (i->container) = head;
	112	tail->next = cur;
	113	cur->prev = tail;
	114	}
	115	else
	116	{
3cb005cf PB	117	head->prev = STATEMENT_LIST_TAIL (i->container);
	118	if (head->prev)
	119	head->prev->next = head;
	120	else
	121	STATEMENT_LIST_HEAD (i->container) = head;
6de9cd9a DN	122	STATEMENT_LIST_TAIL (i->container) = tail;
	123	}
	124
	125	/* Update the iterator, if requested. */
	126	switch (mode)
	127	{
	128	case TSI_NEW_STMT:
	129	case TSI_CONTINUE_LINKING:
	130	case TSI_CHAIN_START:
	131	i->ptr = head;
	132	break;
	133	case TSI_CHAIN_END:
	134	i->ptr = tail;
	135	break;
	136	case TSI_SAME_STMT:
6de9cd9a DN	137	break;
	138	}
	139	}
	140
	141	/* Links a statement, or a chain of statements, after the current stmt. */
	142
	143	void
	144	tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
	145	{
	146	struct tree_statement_list_node head, tail, *cur;
	147
	148	/* Die on looping. */
1e128c5f	149	gcc_assert (t != i->container);
6de9cd9a	150
6de9cd9a DN	151	if (TREE_CODE (t) == STATEMENT_LIST)
	152	{
	153	head = STATEMENT_LIST_HEAD (t);
	154	tail = STATEMENT_LIST_TAIL (t);
	155	STATEMENT_LIST_HEAD (t) = NULL;
	156	STATEMENT_LIST_TAIL (t) = NULL;
	157
	158	free_stmt_list (t);
	159
	160	/* Empty statement lists need no work. */
	161	if (!head \|\| !tail)
	162	{
1e128c5f	163	gcc_assert (head == tail);
6de9cd9a DN	164	return;
	165	}
	166	}
	167	else
	168	{
	169	head = ggc_alloc (sizeof (*head));
	170	head->prev = NULL;
	171	head->next = NULL;
	172	head->stmt = t;
	173	tail = head;
	174	}
	175
325c3691 RH	176	TREE_SIDE_EFFECTS (i->container) = 1;
325c3691 RH	177
6de9cd9a DN	178	cur = i->ptr;
	179
	180	/* Link it into the list. */
	181	if (cur)
	182	{
	183	tail->next = cur->next;
	184	if (tail->next)
	185	tail->next->prev = tail;
	186	else
	187	STATEMENT_LIST_TAIL (i->container) = tail;
	188	head->prev = cur;
	189	cur->next = head;
	190	}
	191	else
	192	{
1e128c5f	193	gcc_assert (!STATEMENT_LIST_TAIL (i->container));
6de9cd9a DN	194	STATEMENT_LIST_HEAD (i->container) = head;
	195	STATEMENT_LIST_TAIL (i->container) = tail;
	196	}
	197
	198	/* Update the iterator, if requested. */
	199	switch (mode)
	200	{
	201	case TSI_NEW_STMT:
	202	case TSI_CHAIN_START:
	203	i->ptr = head;
	204	break;
	205	case TSI_CONTINUE_LINKING:
	206	case TSI_CHAIN_END:
	207	i->ptr = tail;
	208	break;
	209	case TSI_SAME_STMT:
1e128c5f	210	gcc_assert (cur);
6de9cd9a DN	211	break;
	212	}
	213	}
	214
	215	/* Remove a stmt from the tree list. The iterator is updated to point to
	216	the next stmt. */
	217
	218	void
	219	tsi_delink (tree_stmt_iterator *i)
	220	{
	221	struct tree_statement_list_node cur, next, *prev;
	222
	223	cur = i->ptr;
	224	next = cur->next;
	225	prev = cur->prev;
	226
	227	if (prev)
	228	prev->next = next;
	229	else
	230	STATEMENT_LIST_HEAD (i->container) = next;
	231	if (next)
	232	next->prev = prev;
	233	else
	234	STATEMENT_LIST_TAIL (i->container) = prev;
	235
	236	if (!next && !prev)
	237	TREE_SIDE_EFFECTS (i->container) = 0;
	238
	239	i->ptr = next;
	240	}
	241
	242	/* Move all statements in the statement list after I to a new
	243	statement list. I itself is unchanged. */
	244
	245	tree
	246	tsi_split_statement_list_after (const tree_stmt_iterator *i)
	247	{
	248	struct tree_statement_list_node cur, next;
	249	tree old_sl, new_sl;
	250
	251	cur = i->ptr;
	252	/* How can we possibly split after the end, or before the beginning? */
1e128c5f	253	gcc_assert (cur);
6de9cd9a DN	254	next = cur->next;
	255
	256	old_sl = i->container;
	257	new_sl = alloc_stmt_list ();
	258	TREE_SIDE_EFFECTS (new_sl) = 1;
	259
	260	STATEMENT_LIST_HEAD (new_sl) = next;
	261	STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
	262	STATEMENT_LIST_TAIL (old_sl) = cur;
	263	cur->next = NULL;
	264	next->prev = NULL;
	265
	266	return new_sl;
	267	}
	268
	269	/* Move all statements in the statement list before I to a new
	270	statement list. I is set to the head of the new list. */
	271
	272	tree
	273	tsi_split_statement_list_before (tree_stmt_iterator *i)
	274	{
	275	struct tree_statement_list_node cur, prev;
	276	tree old_sl, new_sl;
	277
	278	cur = i->ptr;
	279	/* How can we possibly split after the end, or before the beginning? */
1e128c5f	280	gcc_assert (cur);
6de9cd9a DN	281	prev = cur->prev;
	282
	283	old_sl = i->container;
	284	new_sl = alloc_stmt_list ();
	285	TREE_SIDE_EFFECTS (new_sl) = 1;
	286	i->container = new_sl;
	287
	288	STATEMENT_LIST_HEAD (new_sl) = cur;
	289	STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
	290	STATEMENT_LIST_TAIL (old_sl) = prev;
	291	cur->prev = NULL;
597ae074 JH	292	if (prev)
597ae074 JH	293	prev->next = NULL;
6de9cd9a DN	294
	295	return new_sl;
	296	}
	297
	298	/* Return the first expression in a sequence of COMPOUND_EXPRs,
	299	or in a STATEMENT_LIST. */
	300
	301	tree
	302	expr_first (tree expr)
	303	{
	304	if (expr == NULL_TREE)
	305	return expr;
	306
	307	if (TREE_CODE (expr) == STATEMENT_LIST)
	308	{
	309	struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
	310	return n ? n->stmt : NULL_TREE;
	311	}
	312
	313	while (TREE_CODE (expr) == COMPOUND_EXPR)
	314	expr = TREE_OPERAND (expr, 0);
	315	return expr;
	316	}
	317
	318	/* Return the last expression in a sequence of COMPOUND_EXPRs,
	319	or in a STATEMENT_LIST. */
	320
	321	tree
	322	expr_last (tree expr)
	323	{
	324	if (expr == NULL_TREE)
	325	return expr;
	326
	327	if (TREE_CODE (expr) == STATEMENT_LIST)
	328	{
	329	struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
	330	return n ? n->stmt : NULL_TREE;
	331	}
	332
	333	while (TREE_CODE (expr) == COMPOUND_EXPR)
	334	expr = TREE_OPERAND (expr, 1);
	335	return expr;
	336	}
	337
953ff289 DN	338	/* If EXPR is a single statement return it. If EXPR is a
	339	STATEMENT_LIST containing exactly one statement S, return S.
	340	Otherwise, return NULL. */
6de9cd9a DN	341
	342	tree
	343	expr_only (tree expr)
	344	{
	345	if (expr == NULL_TREE)
	346	return NULL_TREE;
	347
	348	if (TREE_CODE (expr) == STATEMENT_LIST)
	349	{
	350	struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
	351	if (n && STATEMENT_LIST_HEAD (expr) == n)
	352	return n->stmt;
	353	else
	354	return NULL_TREE;
	355	}
	356
	357	if (TREE_CODE (expr) == COMPOUND_EXPR)
	358	return NULL_TREE;
	359
	360	return expr;
	361	}
	362
	363	#include "gt-tree-iterator.h"