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