gcc/tree-iterator.c

   1 /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
   2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Andrew MacLeod  <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License 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 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  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 (""))) VEC(tree,gc) *stmt_list_cache;
  35
  36 tree
  37 alloc_stmt_list (void)
  38 {
  39   tree list;
  40   if (!VEC_empty (tree, stmt_list_cache))
  41     {
  42       list = VEC_pop (tree, stmt_list_cache);
  43       memset (list, 0, sizeof(struct tree_base));
  44       TREE_SET_CODE (list, STATEMENT_LIST);
  45     }
  46   else
  47     list = make_node (STATEMENT_LIST);
  48   TREE_TYPE (list) = void_type_node;
  49   return list;
  50 }
  51
  52 void
  53 free_stmt_list (tree t)
  54 {
  55   gcc_assert (!STATEMENT_LIST_HEAD (t));
  56   gcc_assert (!STATEMENT_LIST_TAIL (t));
  57   VEC_safe_push (tree, gc, stmt_list_cache, t);
  58 }
  59
  60 /* A subroutine of append_to_statement_list{,_force}.  T is not NULL.  */
  61
  62 static void
  63 append_to_statement_list_1 (tree t, tree *list_p)
  64 {
  65   tree list = *list_p;
  66   tree_stmt_iterator i;
  67
  68   if (!list)
  69     {
  70       if (t && TREE_CODE (t) == STATEMENT_LIST)
  71         {
  72           *list_p = t;
  73           return;
  74         }
  75       *list_p = list = alloc_stmt_list ();
  76     }
  77   else if (TREE_CODE (list) != STATEMENT_LIST)
  78     {
  79       tree first = list;
  80       *list_p = list = alloc_stmt_list ();
  81       i = tsi_last (list);
  82       tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
  83     }
  84
  85   i = tsi_last (list);
  86   tsi_link_after (&i, t, TSI_CONTINUE_LINKING);
  87 }
  88
  89 /* Add T to the end of the list container pointed to by LIST_P.
  90    If T is an expression with no effects, it is ignored.  */
  91
  92 void
  93 append_to_statement_list (tree t, tree *list_p)
  94 {
  95   if (t && TREE_SIDE_EFFECTS (t))
  96     append_to_statement_list_1 (t, list_p);
  97 }
  98
  99 /* Similar, but the statement is always added, regardless of side effects.  */
 100
 101 void
 102 append_to_statement_list_force (tree t, tree *list_p)
 103 {
 104   if (t != NULL_TREE)
 105     append_to_statement_list_1 (t, list_p);
 106 }
 107
 108 /* Links a statement, or a chain of statements, before the current stmt.  */
 109
 110 void
 111 tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 112 {
 113   struct tree_statement_list_node *head, *tail, *cur;
 114
 115   /* Die on looping.  */
 116   gcc_assert (t != i->container);
 117
 118   if (TREE_CODE (t) == STATEMENT_LIST)
 119     {
 120       head = STATEMENT_LIST_HEAD (t);
 121       tail = STATEMENT_LIST_TAIL (t);
 122       STATEMENT_LIST_HEAD (t) = NULL;
 123       STATEMENT_LIST_TAIL (t) = NULL;
 124
 125       free_stmt_list (t);
 126
 127       /* Empty statement lists need no work.  */
 128       if (!head || !tail)
 129         {
 130           gcc_assert (head == tail);
 131           return;
 132         }
 133     }
 134   else
 135     {
 136       head = ggc_alloc_tree_statement_list_node ();
 137       head->prev = NULL;
 138       head->next = NULL;
 139       head->stmt = t;
 140       tail = head;
 141     }
 142
 143   TREE_SIDE_EFFECTS (i->container) = 1;
 144
 145   cur = i->ptr;
 146
 147   /* Link it into the list.  */
 148   if (cur)
 149     {
 150       head->prev = cur->prev;
 151       if (head->prev)
 152         head->prev->next = head;
 153       else
 154         STATEMENT_LIST_HEAD (i->container) = head;
 155       tail->next = cur;
 156       cur->prev = tail;
 157     }
 158   else
 159     {
 160       head->prev = STATEMENT_LIST_TAIL (i->container);
 161       if (head->prev)
 162        head->prev->next = head;
 163       else
 164        STATEMENT_LIST_HEAD (i->container) = head;
 165       STATEMENT_LIST_TAIL (i->container) = tail;
 166     }
 167
 168   /* Update the iterator, if requested.  */
 169   switch (mode)
 170     {
 171     case TSI_NEW_STMT:
 172     case TSI_CONTINUE_LINKING:
 173     case TSI_CHAIN_START:
 174       i->ptr = head;
 175       break;
 176     case TSI_CHAIN_END:
 177       i->ptr = tail;
 178       break;
 179     case TSI_SAME_STMT:
 180       break;
 181     }
 182 }
 183
 184 /* Links a statement, or a chain of statements, after the current stmt.  */
 185
 186 void
 187 tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 188 {
 189   struct tree_statement_list_node *head, *tail, *cur;
 190
 191   /* Die on looping.  */
 192   gcc_assert (t != i->container);
 193
 194   if (TREE_CODE (t) == STATEMENT_LIST)
 195     {
 196       head = STATEMENT_LIST_HEAD (t);
 197       tail = STATEMENT_LIST_TAIL (t);
 198       STATEMENT_LIST_HEAD (t) = NULL;
 199       STATEMENT_LIST_TAIL (t) = NULL;
 200
 201       free_stmt_list (t);
 202
 203       /* Empty statement lists need no work.  */
 204       if (!head || !tail)
 205         {
 206           gcc_assert (head == tail);
 207           return;
 208         }
 209     }
 210   else
 211     {
 212       head = ggc_alloc_tree_statement_list_node ();
 213       head->prev = NULL;
 214       head->next = NULL;
 215       head->stmt = t;
 216       tail = head;
 217     }
 218
 219   TREE_SIDE_EFFECTS (i->container) = 1;
 220
 221   cur = i->ptr;
 222
 223   /* Link it into the list.  */
 224   if (cur)
 225     {
 226       tail->next = cur->next;
 227       if (tail->next)
 228         tail->next->prev = tail;
 229       else
 230         STATEMENT_LIST_TAIL (i->container) = tail;
 231       head->prev = cur;
 232       cur->next = head;
 233     }
 234   else
 235     {
 236       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 237       STATEMENT_LIST_HEAD (i->container) = head;
 238       STATEMENT_LIST_TAIL (i->container) = tail;
 239     }
 240
 241   /* Update the iterator, if requested.  */
 242   switch (mode)
 243     {
 244     case TSI_NEW_STMT:
 245     case TSI_CHAIN_START:
 246       i->ptr = head;
 247       break;
 248     case TSI_CONTINUE_LINKING:
 249     case TSI_CHAIN_END:
 250       i->ptr = tail;
 251       break;
 252     case TSI_SAME_STMT:
 253       gcc_assert (cur);
 254       break;
 255     }
 256 }
 257
 258 /* Remove a stmt from the tree list.  The iterator is updated to point to
 259    the next stmt.  */
 260
 261 void
 262 tsi_delink (tree_stmt_iterator *i)
 263 {
 264   struct tree_statement_list_node *cur, *next, *prev;
 265
 266   cur = i->ptr;
 267   next = cur->next;
 268   prev = cur->prev;
 269
 270   if (prev)
 271     prev->next = next;
 272   else
 273     STATEMENT_LIST_HEAD (i->container) = next;
 274   if (next)
 275     next->prev = prev;
 276   else
 277     STATEMENT_LIST_TAIL (i->container) = prev;
 278
 279   if (!next && !prev)
 280     TREE_SIDE_EFFECTS (i->container) = 0;
 281
 282   i->ptr = next;
 283 }
 284
 285 /* Return the first expression in a sequence of COMPOUND_EXPRs,
 286    or in a STATEMENT_LIST.  */
 287
 288 tree
 289 expr_first (tree expr)
 290 {
 291   if (expr == NULL_TREE)
 292     return expr;
 293
 294   if (TREE_CODE (expr) == STATEMENT_LIST)
 295     {
 296       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 297       return n ? n->stmt : NULL_TREE;
 298     }
 299
 300   while (TREE_CODE (expr) == COMPOUND_EXPR)
 301     expr = TREE_OPERAND (expr, 0);
 302
 303   return expr;
 304 }
 305
 306 /* Return the last expression in a sequence of COMPOUND_EXPRs,
 307    or in a STATEMENT_LIST.  */
 308
 309 tree
 310 expr_last (tree expr)
 311 {
 312   if (expr == NULL_TREE)
 313     return expr;
 314
 315   if (TREE_CODE (expr) == STATEMENT_LIST)
 316     {
 317       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 318       return n ? n->stmt : NULL_TREE;
 319     }
 320
 321   while (TREE_CODE (expr) == COMPOUND_EXPR)
 322     expr = TREE_OPERAND (expr, 1);
 323
 324   return expr;
 325 }
 326
 327 #include "gt-tree-iterator.h"