gcc/tree-iterator.c

   1 /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
   2    Copyright (C) 2003-2020 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     {
  45       list = make_node (STATEMENT_LIST);
  46       TREE_SIDE_EFFECTS (list) = 0;
  47     }
  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 (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   else if (TREE_CODE (list) != STATEMENT_LIST)
  78     {
  79       tree first = list;
  80       *list_p = list = alloc_stmt_list ();
  81       i = tsi_last (list);
  82       tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
  83     }
  84
  85   i = tsi_last (list);
  86   tsi_link_after (&i, t, TSI_CONTINUE_LINKING);
  87 }
  88
  89 /* Add T to the end of the list container pointed to by LIST_P.
  90    If T is an expression with no effects, it is ignored.  */
  91
  92 void
  93 append_to_statement_list (tree t, tree *list_p)
  94 {
  95   if (t && (TREE_SIDE_EFFECTS (t) || TREE_CODE (t) == DEBUG_BEGIN_STMT))
  96     append_to_statement_list_1 (t, list_p);
  97 }
  98
  99 /* Similar, but the statement is always added, regardless of side effects.  */
 100
 101 void
 102 append_to_statement_list_force (tree t, tree *list_p)
 103 {
 104   if (t != NULL_TREE)
 105     append_to_statement_list_1 (t, list_p);
 106 }
 107
 108 /* Links a statement, or a chain of statements, before the current stmt.  */
 109
 110 void
 111 tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 112 {
 113   struct tree_statement_list_node *head, *tail, *cur;
 114
 115   /* Die on looping.  */
 116   gcc_assert (t != i->container);
 117
 118   if (TREE_CODE (t) == STATEMENT_LIST)
 119     {
 120       head = STATEMENT_LIST_HEAD (t);
 121       tail = STATEMENT_LIST_TAIL (t);
 122       STATEMENT_LIST_HEAD (t) = NULL;
 123       STATEMENT_LIST_TAIL (t) = NULL;
 124
 125       free_stmt_list (t);
 126
 127       /* Empty statement lists need no work.  */
 128       if (!head || !tail)
 129         {
 130           gcc_assert (head == tail);
 131           return;
 132         }
 133     }
 134   else
 135     {
 136       head = ggc_alloc<tree_statement_list_node> ();
 137       head->prev = NULL;
 138       head->next = NULL;
 139       head->stmt = t;
 140       tail = head;
 141     }
 142
 143   if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
 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   if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
 221     TREE_SIDE_EFFECTS (i->container) = 1;
 222
 223   cur = i->ptr;
 224
 225   /* Link it into the list.  */
 226   if (cur)
 227     {
 228       tail->next = cur->next;
 229       if (tail->next)
 230         tail->next->prev = tail;
 231       else
 232         STATEMENT_LIST_TAIL (i->container) = tail;
 233       head->prev = cur;
 234       cur->next = head;
 235     }
 236   else
 237     {
 238       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 239       STATEMENT_LIST_HEAD (i->container) = head;
 240       STATEMENT_LIST_TAIL (i->container) = tail;
 241     }
 242
 243   /* Update the iterator, if requested.  */
 244   switch (mode)
 245     {
 246     case TSI_NEW_STMT:
 247     case TSI_CHAIN_START:
 248       i->ptr = head;
 249       break;
 250     case TSI_CONTINUE_LINKING:
 251     case TSI_CHAIN_END:
 252       i->ptr = tail;
 253       break;
 254     case TSI_SAME_STMT:
 255       gcc_assert (cur);
 256       break;
 257     }
 258 }
 259
 260 /* Remove a stmt from the tree list.  The iterator is updated to point to
 261    the next stmt.  */
 262
 263 void
 264 tsi_delink (tree_stmt_iterator *i)
 265 {
 266   struct tree_statement_list_node *cur, *next, *prev;
 267
 268   cur = i->ptr;
 269   next = cur->next;
 270   prev = cur->prev;
 271
 272   if (prev)
 273     prev->next = next;
 274   else
 275     STATEMENT_LIST_HEAD (i->container) = next;
 276   if (next)
 277     next->prev = prev;
 278   else
 279     STATEMENT_LIST_TAIL (i->container) = prev;
 280
 281   if (!next && !prev)
 282     TREE_SIDE_EFFECTS (i->container) = 0;
 283
 284   i->ptr = next;
 285 }
 286
 287 /* Return the first expression in a sequence of COMPOUND_EXPRs, or in
 288    a STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
 289    STATEMENT_LIST if that's the first non-DEBUG_BEGIN_STMT.  */
 290
 291 tree
 292 expr_first (tree expr)
 293 {
 294   if (expr == NULL_TREE)
 295     return expr;
 296
 297   if (TREE_CODE (expr) == STATEMENT_LIST)
 298     {
 299       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 300       if (!n)
 301         return NULL_TREE;
 302       while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
 303         {
 304           n = n->next;
 305           if (!n)
 306             return NULL_TREE;
 307         }
 308       /* If the first non-debug stmt is not a statement list, we
 309          already know it's what we're looking for.  */
 310       if (TREE_CODE (n->stmt) != STATEMENT_LIST)
 311         return n->stmt;
 312
 313       return expr_first (n->stmt);
 314     }
 315
 316   while (TREE_CODE (expr) == COMPOUND_EXPR)
 317     expr = TREE_OPERAND (expr, 0);
 318
 319   return expr;
 320 }
 321
 322 /* Return the last expression in a sequence of COMPOUND_EXPRs, or in a
 323    STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
 324    STATEMENT_LIST if that's the last non-DEBUG_BEGIN_STMT.  */
 325
 326 tree
 327 expr_last (tree expr)
 328 {
 329   if (expr == NULL_TREE)
 330     return expr;
 331
 332   if (TREE_CODE (expr) == STATEMENT_LIST)
 333     {
 334       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 335       if (!n)
 336         return NULL_TREE;
 337       while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
 338         {
 339           n = n->prev;
 340           if (!n)
 341             return NULL_TREE;
 342         }
 343       /* If the last non-debug stmt is not a statement list, we
 344          already know it's what we're looking for.  */
 345       if (TREE_CODE (n->stmt) != STATEMENT_LIST)
 346         return n->stmt;
 347
 348       return expr_last (n->stmt);
 349     }
 350
 351   while (TREE_CODE (expr) == COMPOUND_EXPR)
 352     expr = TREE_OPERAND (expr, 1);
 353
 354   return expr;
 355 }
 356
 357 /* If EXPR is a STATEMENT_LIST containing just DEBUG_BEGIN_STMTs and
 358    a single other stmt, return that other stmt (recursively).
 359    If it is a STATEMENT_LIST containing no non-DEBUG_BEGIN_STMTs or
 360    multiple, return NULL_TREE.
 361    Otherwise return EXPR.  */
 362
 363 tree
 364 expr_single (tree expr)
 365 {
 366   if (expr == NULL_TREE)
 367     return expr;
 368
 369   if (TREE_CODE (expr) == STATEMENT_LIST)
 370     {
 371       /* With -gstatement-frontiers we could have a STATEMENT_LIST with
 372          DEBUG_BEGIN_STMT(s) and only a single other stmt, which with
 373          -g wouldn't be present and we'd have that single other stmt
 374          directly instead.  */
 375       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 376       if (!n)
 377         return NULL_TREE;
 378       while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
 379         {
 380           n = n->next;
 381           if (!n)
 382             return NULL_TREE;
 383         }
 384       expr = n->stmt;
 385       do
 386         {
 387           n = n->next;
 388           if (!n)
 389             return expr_single (expr);
 390         }
 391       while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT);
 392       return NULL_TREE;
 393     }
 394
 395   return expr;
 396 }
 397
 398 #include "gt-tree-iterator.h"