gcc/tree-iterator.c

   1 /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
   2    Copyright (C) 2003, 2004, 2007, 2008, 2009 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 3, 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 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 "tree.h"
  25 #include "gimple.h"
  26 #include "tree-iterator.h"
  27 #include "ggc.h"
  28
  29
  30 /* This is a cache of STATEMENT_LIST nodes.  We create and destroy them
  31    fairly often during gimplification.  */
  32
  33 static GTY ((deletable (""))) tree stmt_list_cache;
  34
  35 tree
  36 alloc_stmt_list (void)
  37 {
  38   tree list = stmt_list_cache;
  39   if (list)
  40     {
  41       stmt_list_cache = TREE_CHAIN (list);
  42       gcc_assert (stmt_list_cache != list);
  43       memset (list, 0, sizeof(struct tree_common));
  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   /* If this triggers, it's a sign that the same list is being freed
  58      twice.  */
  59   gcc_assert (t != stmt_list_cache || stmt_list_cache == NULL);
  60   TREE_CHAIN (t) = stmt_list_cache;
  61   stmt_list_cache = t;
  62 }
  63
  64 /* A subroutine of append_to_statement_list{,_force}.  T is not NULL.  */
  65
  66 static void
  67 append_to_statement_list_1 (tree t, tree *list_p)
  68 {
  69   tree list = *list_p;
  70   tree_stmt_iterator i;
  71
  72   if (!list)
  73     {
  74       if (t && TREE_CODE (t) == STATEMENT_LIST)
  75         {
  76           *list_p = t;
  77           return;
  78         }
  79       *list_p = list = alloc_stmt_list ();
  80     }
  81
  82   i = tsi_last (list);
  83   tsi_link_after (&i, t, TSI_CONTINUE_LINKING);
  84 }
  85
  86 /* Add T to the end of the list container pointed to by LIST_P.
  87    If T is an expression with no effects, it is ignored.  */
  88
  89 void
  90 append_to_statement_list (tree t, tree *list_p)
  91 {
  92   if (t && TREE_SIDE_EFFECTS (t))
  93     append_to_statement_list_1 (t, list_p);
  94 }
  95
  96 /* Similar, but the statement is always added, regardless of side effects.  */
  97
  98 void
  99 append_to_statement_list_force (tree t, tree *list_p)
 100 {
 101   if (t != NULL_TREE)
 102     append_to_statement_list_1 (t, list_p);
 103 }
 104
 105 /* Links a statement, or a chain of statements, before the current stmt.  */
 106
 107 void
 108 tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 109 {
 110   struct tree_statement_list_node *head, *tail, *cur;
 111
 112   /* Die on looping.  */
 113   gcc_assert (t != i->container);
 114
 115   if (TREE_CODE (t) == STATEMENT_LIST)
 116     {
 117       head = STATEMENT_LIST_HEAD (t);
 118       tail = STATEMENT_LIST_TAIL (t);
 119       STATEMENT_LIST_HEAD (t) = NULL;
 120       STATEMENT_LIST_TAIL (t) = NULL;
 121
 122       free_stmt_list (t);
 123
 124       /* Empty statement lists need no work.  */
 125       if (!head || !tail)
 126         {
 127           gcc_assert (head == tail);
 128           return;
 129         }
 130     }
 131   else
 132     {
 133       head = ggc_alloc_tree_statement_list_node ();
 134       head->prev = NULL;
 135       head->next = NULL;
 136       head->stmt = t;
 137       tail = head;
 138     }
 139
 140   TREE_SIDE_EFFECTS (i->container) = 1;
 141
 142   cur = i->ptr;
 143
 144   /* Link it into the list.  */
 145   if (cur)
 146     {
 147       head->prev = cur->prev;
 148       if (head->prev)
 149         head->prev->next = head;
 150       else
 151         STATEMENT_LIST_HEAD (i->container) = head;
 152       tail->next = cur;
 153       cur->prev = tail;
 154     }
 155   else
 156     {
 157       head->prev = STATEMENT_LIST_TAIL (i->container);
 158       if (head->prev)
 159        head->prev->next = head;
 160       else
 161        STATEMENT_LIST_HEAD (i->container) = head;
 162       STATEMENT_LIST_TAIL (i->container) = tail;
 163     }
 164
 165   /* Update the iterator, if requested.  */
 166   switch (mode)
 167     {
 168     case TSI_NEW_STMT:
 169     case TSI_CONTINUE_LINKING:
 170     case TSI_CHAIN_START:
 171       i->ptr = head;
 172       break;
 173     case TSI_CHAIN_END:
 174       i->ptr = tail;
 175       break;
 176     case TSI_SAME_STMT:
 177       break;
 178     }
 179 }
 180
 181 /* Links a statement, or a chain of statements, after the current stmt.  */
 182
 183 void
 184 tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 185 {
 186   struct tree_statement_list_node *head, *tail, *cur;
 187
 188   /* Die on looping.  */
 189   gcc_assert (t != i->container);
 190
 191   if (TREE_CODE (t) == STATEMENT_LIST)
 192     {
 193       head = STATEMENT_LIST_HEAD (t);
 194       tail = STATEMENT_LIST_TAIL (t);
 195       STATEMENT_LIST_HEAD (t) = NULL;
 196       STATEMENT_LIST_TAIL (t) = NULL;
 197
 198       free_stmt_list (t);
 199
 200       /* Empty statement lists need no work.  */
 201       if (!head || !tail)
 202         {
 203           gcc_assert (head == tail);
 204           return;
 205         }
 206     }
 207   else
 208     {
 209       head = ggc_alloc_tree_statement_list_node ();
 210       head->prev = NULL;
 211       head->next = NULL;
 212       head->stmt = t;
 213       tail = head;
 214     }
 215
 216   TREE_SIDE_EFFECTS (i->container) = 1;
 217
 218   cur = i->ptr;
 219
 220   /* Link it into the list.  */
 221   if (cur)
 222     {
 223       tail->next = cur->next;
 224       if (tail->next)
 225         tail->next->prev = tail;
 226       else
 227         STATEMENT_LIST_TAIL (i->container) = tail;
 228       head->prev = cur;
 229       cur->next = head;
 230     }
 231   else
 232     {
 233       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 234       STATEMENT_LIST_HEAD (i->container) = head;
 235       STATEMENT_LIST_TAIL (i->container) = tail;
 236     }
 237
 238   /* Update the iterator, if requested.  */
 239   switch (mode)
 240     {
 241     case TSI_NEW_STMT:
 242     case TSI_CHAIN_START:
 243       i->ptr = head;
 244       break;
 245     case TSI_CONTINUE_LINKING:
 246     case TSI_CHAIN_END:
 247       i->ptr = tail;
 248       break;
 249     case TSI_SAME_STMT:
 250       gcc_assert (cur);
 251       break;
 252     }
 253 }
 254
 255 /* Remove a stmt from the tree list.  The iterator is updated to point to
 256    the next stmt.  */
 257
 258 void
 259 tsi_delink (tree_stmt_iterator *i)
 260 {
 261   struct tree_statement_list_node *cur, *next, *prev;
 262
 263   cur = i->ptr;
 264   next = cur->next;
 265   prev = cur->prev;
 266
 267   if (prev)
 268     prev->next = next;
 269   else
 270     STATEMENT_LIST_HEAD (i->container) = next;
 271   if (next)
 272     next->prev = prev;
 273   else
 274     STATEMENT_LIST_TAIL (i->container) = prev;
 275
 276   if (!next && !prev)
 277     TREE_SIDE_EFFECTS (i->container) = 0;
 278
 279   i->ptr = next;
 280 }
 281
 282 /* Return the first expression in a sequence of COMPOUND_EXPRs,
 283    or in a STATEMENT_LIST.  */
 284
 285 tree
 286 expr_first (tree expr)
 287 {
 288   if (expr == NULL_TREE)
 289     return expr;
 290
 291   if (TREE_CODE (expr) == STATEMENT_LIST)
 292     {
 293       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 294       return n ? n->stmt : NULL_TREE;
 295     }
 296
 297   while (TREE_CODE (expr) == COMPOUND_EXPR)
 298     expr = TREE_OPERAND (expr, 0);
 299
 300   return expr;
 301 }
 302
 303 /* Return the last expression in a sequence of COMPOUND_EXPRs,
 304    or in a STATEMENT_LIST.  */
 305
 306 tree
 307 expr_last (tree expr)
 308 {
 309   if (expr == NULL_TREE)
 310     return expr;
 311
 312   if (TREE_CODE (expr) == STATEMENT_LIST)
 313     {
 314       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 315       return n ? n->stmt : NULL_TREE;
 316     }
 317
 318   while (TREE_CODE (expr) == COMPOUND_EXPR)
 319     expr = TREE_OPERAND (expr, 1);
 320
 321   return expr;
 322 }
 323
 324 #include "gt-tree-iterator.h"