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