gcc/tree-iterator.c

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