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