gcc/tree-iterator.c

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