gcc/tree-iterator.c

   1 /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
   2    Copyright (C) 2003-2017 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 "tree-iterator.h"
  26
  27
  28 /* This is a cache of STATEMENT_LIST nodes.  We create and destroy them
  29    fairly often during gimplification.  */
  30
  31 static GTY ((deletable (""))) vec<tree, va_gc> *stmt_list_cache;
  32
  33 tree
  34 alloc_stmt_list (void)
  35 {
  36   tree list;
  37   if (!vec_safe_is_empty (stmt_list_cache))
  38     {
  39       list = stmt_list_cache->pop ();
  40       memset (list, 0, sizeof (struct tree_base));
  41       TREE_SET_CODE (list, STATEMENT_LIST);
  42     }
  43   else
  44     list = make_node (STATEMENT_LIST);
  45   TREE_TYPE (list) = void_type_node;
  46   return list;
  47 }
  48
  49 void
  50 free_stmt_list (tree t)
  51 {
  52   gcc_assert (!STATEMENT_LIST_HEAD (t));
  53   gcc_assert (!STATEMENT_LIST_TAIL (t));
  54   vec_safe_push (stmt_list_cache, t);
  55 }
  56
  57 /* A subroutine of append_to_statement_list{,_force}.  T is not NULL.  */
  58
  59 static void
  60 append_to_statement_list_1 (tree t, tree *list_p)
  61 {
  62   tree list = *list_p;
  63   tree_stmt_iterator i;
  64
  65   if (!list)
  66     {
  67       if (t && TREE_CODE (t) == STATEMENT_LIST)
  68         {
  69           *list_p = t;
  70           return;
  71         }
  72       *list_p = list = alloc_stmt_list ();
  73     }
  74   else if (TREE_CODE (list) != STATEMENT_LIST)
  75     {
  76       tree first = list;
  77       *list_p = list = alloc_stmt_list ();
  78       i = tsi_last (list);
  79       tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
  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) || TREE_CODE (t) == DEBUG_BEGIN_STMT))
  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   if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
 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   if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
 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, or in
 285    a STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
 286    STATEMENT_LIST if that's the first non-DEBUG_BEGIN_STMT.  */
 287
 288 tree
 289 expr_first (tree expr)
 290 {
 291   if (expr == NULL_TREE)
 292     return expr;
 293
 294   if (TREE_CODE (expr) == STATEMENT_LIST)
 295     {
 296       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 297       if (!n)
 298         return NULL_TREE;
 299       while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
 300         {
 301           n = n->next;
 302           if (!n)
 303             return NULL_TREE;
 304         }
 305       /* If the first non-debug stmt is not a statement list, we
 306          already know it's what we're looking for.  */
 307       if (TREE_CODE (n->stmt) != STATEMENT_LIST)
 308         return n->stmt;
 309
 310       return expr_first (n->stmt);
 311     }
 312
 313   while (TREE_CODE (expr) == COMPOUND_EXPR)
 314     expr = TREE_OPERAND (expr, 0);
 315
 316   return expr;
 317 }
 318
 319 /* Return the last expression in a sequence of COMPOUND_EXPRs, or in a
 320    STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
 321    STATEMENT_LIST if that's the last non-DEBUG_BEGIN_STMT.  */
 322
 323 tree
 324 expr_last (tree expr)
 325 {
 326   if (expr == NULL_TREE)
 327     return expr;
 328
 329   if (TREE_CODE (expr) == STATEMENT_LIST)
 330     {
 331       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 332       if (!n)
 333         return NULL_TREE;
 334       while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
 335         {
 336           n = n->prev;
 337           if (!n)
 338             return NULL_TREE;
 339         }
 340       /* If the last non-debug stmt is not a statement list, we
 341          already know it's what we're looking for.  */
 342       if (TREE_CODE (n->stmt) != STATEMENT_LIST)
 343         return n->stmt;
 344
 345       return expr_last (n->stmt);
 346     }
 347
 348   while (TREE_CODE (expr) == COMPOUND_EXPR)
 349     expr = TREE_OPERAND (expr, 1);
 350
 351   return expr;
 352 }
 353
 354 #include "gt-tree-iterator.h"