gcc/tree-iterator.c

   1 /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
   2    Copyright (C) 2003, 2004 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 2, 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 COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tree.h"
  26 #include "tree-gimple.h"
  27 #include "tree-iterator.h"
  28 #include "ggc.h"
  29
  30
  31 /* This is a cache of STATEMENT_LIST nodes.  We create and destroy them
  32    fairly often during gimplification.  */
  33
  34 static GTY ((deletable (""))) tree stmt_list_cache;
  35
  36 tree
  37 alloc_stmt_list (void)
  38 {
  39   tree list = stmt_list_cache;
  40   if (list)
  41     {
  42       stmt_list_cache = TREE_CHAIN (list);
  43       memset (list, 0, sizeof(struct tree_common));
  44       TREE_SET_CODE (list, STATEMENT_LIST);
  45     }
  46   else
  47     list = make_node (STATEMENT_LIST);
  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   TREE_CHAIN (t) = stmt_list_cache;
  58   stmt_list_cache = t;
  59 }
  60
  61 /* Links a statement, or a chain of statements, before the current stmt.  */
  62
  63 void
  64 tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
  65 {
  66   struct tree_statement_list_node *head, *tail, *cur;
  67
  68   /* Die on looping.  */
  69   gcc_assert (t != i->container);
  70
  71   if (TREE_CODE (t) == STATEMENT_LIST)
  72     {
  73       head = STATEMENT_LIST_HEAD (t);
  74       tail = STATEMENT_LIST_TAIL (t);
  75       STATEMENT_LIST_HEAD (t) = NULL;
  76       STATEMENT_LIST_TAIL (t) = NULL;
  77
  78       free_stmt_list (t);
  79
  80       /* Empty statement lists need no work.  */
  81       if (!head || !tail)
  82         {
  83           gcc_assert (head == tail);
  84           return;
  85         }
  86     }
  87   else
  88     {
  89       head = ggc_alloc (sizeof (*head));
  90       head->prev = NULL;
  91       head->next = NULL;
  92       head->stmt = t;
  93       tail = head;
  94     }
  95
  96   TREE_SIDE_EFFECTS (i->container) = 1;
  97
  98   cur = i->ptr;
  99
 100   /* Link it into the list.  */
 101   if (cur)
 102     {
 103       head->prev = cur->prev;
 104       if (head->prev)
 105         head->prev->next = head;
 106       else
 107         STATEMENT_LIST_HEAD (i->container) = head;
 108       tail->next = cur;
 109       cur->prev = tail;
 110     }
 111   else
 112     {
 113       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 114       STATEMENT_LIST_HEAD (i->container) = head;
 115       STATEMENT_LIST_TAIL (i->container) = tail;
 116     }
 117
 118   /* Update the iterator, if requested.  */
 119   switch (mode)
 120     {
 121     case TSI_NEW_STMT:
 122     case TSI_CONTINUE_LINKING:
 123     case TSI_CHAIN_START:
 124       i->ptr = head;
 125       break;
 126     case TSI_CHAIN_END:
 127       i->ptr = tail;
 128       break;
 129     case TSI_SAME_STMT:
 130       gcc_assert (cur);
 131       break;
 132     }
 133 }
 134
 135 /* Links a statement, or a chain of statements, after the current stmt.  */
 136
 137 void
 138 tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 139 {
 140   struct tree_statement_list_node *head, *tail, *cur;
 141
 142   /* Die on looping.  */
 143   gcc_assert (t != i->container);
 144
 145   if (TREE_CODE (t) == STATEMENT_LIST)
 146     {
 147       head = STATEMENT_LIST_HEAD (t);
 148       tail = STATEMENT_LIST_TAIL (t);
 149       STATEMENT_LIST_HEAD (t) = NULL;
 150       STATEMENT_LIST_TAIL (t) = NULL;
 151
 152       free_stmt_list (t);
 153
 154       /* Empty statement lists need no work.  */
 155       if (!head || !tail)
 156         {
 157           gcc_assert (head == tail);
 158           return;
 159         }
 160     }
 161   else
 162     {
 163       head = ggc_alloc (sizeof (*head));
 164       head->prev = NULL;
 165       head->next = NULL;
 166       head->stmt = t;
 167       tail = head;
 168     }
 169
 170   TREE_SIDE_EFFECTS (i->container) = 1;
 171
 172   cur = i->ptr;
 173
 174   /* Link it into the list.  */
 175   if (cur)
 176     {
 177       tail->next = cur->next;
 178       if (tail->next)
 179         tail->next->prev = tail;
 180       else
 181         STATEMENT_LIST_TAIL (i->container) = tail;
 182       head->prev = cur;
 183       cur->next = head;
 184     }
 185   else
 186     {
 187       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 188       STATEMENT_LIST_HEAD (i->container) = head;
 189       STATEMENT_LIST_TAIL (i->container) = tail;
 190     }
 191
 192   /* Update the iterator, if requested.  */
 193   switch (mode)
 194     {
 195     case TSI_NEW_STMT:
 196     case TSI_CHAIN_START:
 197       i->ptr = head;
 198       break;
 199     case TSI_CONTINUE_LINKING:
 200     case TSI_CHAIN_END:
 201       i->ptr = tail;
 202       break;
 203     case TSI_SAME_STMT:
 204       gcc_assert (cur);
 205       break;
 206     }
 207 }
 208
 209 /* Remove a stmt from the tree list.  The iterator is updated to point to
 210    the next stmt.  */
 211
 212 void
 213 tsi_delink (tree_stmt_iterator *i)
 214 {
 215   struct tree_statement_list_node *cur, *next, *prev;
 216
 217   cur = i->ptr;
 218   next = cur->next;
 219   prev = cur->prev;
 220
 221   if (prev)
 222     prev->next = next;
 223   else
 224     STATEMENT_LIST_HEAD (i->container) = next;
 225   if (next)
 226     next->prev = prev;
 227   else
 228     STATEMENT_LIST_TAIL (i->container) = prev;
 229
 230   if (!next && !prev)
 231     TREE_SIDE_EFFECTS (i->container) = 0;
 232
 233   i->ptr = next;
 234 }
 235
 236 /* Move all statements in the statement list after I to a new
 237    statement list.  I itself is unchanged.  */
 238
 239 tree
 240 tsi_split_statement_list_after (const tree_stmt_iterator *i)
 241 {
 242   struct tree_statement_list_node *cur, *next;
 243   tree old_sl, new_sl;
 244
 245   cur = i->ptr;
 246   /* How can we possibly split after the end, or before the beginning?  */
 247   gcc_assert (cur);
 248   next = cur->next;
 249
 250   old_sl = i->container;
 251   new_sl = alloc_stmt_list ();
 252   TREE_SIDE_EFFECTS (new_sl) = 1;
 253
 254   STATEMENT_LIST_HEAD (new_sl) = next;
 255   STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
 256   STATEMENT_LIST_TAIL (old_sl) = cur;
 257   cur->next = NULL;
 258   next->prev = NULL;
 259
 260   return new_sl;
 261 }
 262
 263 /* Move all statements in the statement list before I to a new
 264    statement list.  I is set to the head of the new list.  */
 265
 266 tree
 267 tsi_split_statement_list_before (tree_stmt_iterator *i)
 268 {
 269   struct tree_statement_list_node *cur, *prev;
 270   tree old_sl, new_sl;
 271
 272   cur = i->ptr;
 273   /* How can we possibly split after the end, or before the beginning?  */
 274   gcc_assert (cur);
 275   prev = cur->prev;
 276
 277   old_sl = i->container;
 278   new_sl = alloc_stmt_list ();
 279   TREE_SIDE_EFFECTS (new_sl) = 1;
 280   i->container = new_sl;
 281
 282   STATEMENT_LIST_HEAD (new_sl) = cur;
 283   STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
 284   STATEMENT_LIST_TAIL (old_sl) = prev;
 285   cur->prev = NULL;
 286   prev->next = NULL;
 287
 288   return new_sl;
 289 }
 290
 291 /* Return the first expression in a sequence of COMPOUND_EXPRs,
 292    or in a STATEMENT_LIST.  */
 293
 294 tree
 295 expr_first (tree expr)
 296 {
 297   if (expr == NULL_TREE)
 298     return expr;
 299
 300   if (TREE_CODE (expr) == STATEMENT_LIST)
 301     {
 302       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 303       return n ? n->stmt : NULL_TREE;
 304     }
 305
 306   while (TREE_CODE (expr) == COMPOUND_EXPR)
 307     expr = TREE_OPERAND (expr, 0);
 308   return expr;
 309 }
 310
 311 /* Return the last expression in a sequence of COMPOUND_EXPRs,
 312    or in a STATEMENT_LIST.  */
 313
 314 tree
 315 expr_last (tree expr)
 316 {
 317   if (expr == NULL_TREE)
 318     return expr;
 319
 320   if (TREE_CODE (expr) == STATEMENT_LIST)
 321     {
 322       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 323       return n ? n->stmt : NULL_TREE;
 324     }
 325
 326   while (TREE_CODE (expr) == COMPOUND_EXPR)
 327     expr = TREE_OPERAND (expr, 1);
 328   return expr;
 329 }
 330
 331 /* If EXPR is a single statement, naked or in a STATEMENT_LIST, then
 332    return it.  Otherwise return NULL.  */
 333
 334 tree
 335 expr_only (tree expr)
 336 {
 337   if (expr == NULL_TREE)
 338     return NULL_TREE;
 339
 340   if (TREE_CODE (expr) == STATEMENT_LIST)
 341     {
 342       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 343       if (n && STATEMENT_LIST_HEAD (expr) == n)
 344         return n->stmt;
 345       else
 346         return NULL_TREE;
 347     }
 348
 349   if (TREE_CODE (expr) == COMPOUND_EXPR)
 350     return NULL_TREE;
 351
 352   return expr;
 353 }
 354
 355 #include "gt-tree-iterator.h"