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       head->prev = STATEMENT_LIST_TAIL (i->container);
 114       if (head->prev)
 115        head->prev->next = head;
 116       else
 117        STATEMENT_LIST_HEAD (i->container) = head;
 118       STATEMENT_LIST_TAIL (i->container) = tail;
 119     }
 120
 121   /* Update the iterator, if requested.  */
 122   switch (mode)
 123     {
 124     case TSI_NEW_STMT:
 125     case TSI_CONTINUE_LINKING:
 126     case TSI_CHAIN_START:
 127       i->ptr = head;
 128       break;
 129     case TSI_CHAIN_END:
 130       i->ptr = tail;
 131       break;
 132     case TSI_SAME_STMT:
 133       break;
 134     }
 135 }
 136
 137 /* Links a statement, or a chain of statements, after the current stmt.  */
 138
 139 void
 140 tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 141 {
 142   struct tree_statement_list_node *head, *tail, *cur;
 143
 144   /* Die on looping.  */
 145   gcc_assert (t != i->container);
 146
 147   if (TREE_CODE (t) == STATEMENT_LIST)
 148     {
 149       head = STATEMENT_LIST_HEAD (t);
 150       tail = STATEMENT_LIST_TAIL (t);
 151       STATEMENT_LIST_HEAD (t) = NULL;
 152       STATEMENT_LIST_TAIL (t) = NULL;
 153
 154       free_stmt_list (t);
 155
 156       /* Empty statement lists need no work.  */
 157       if (!head || !tail)
 158         {
 159           gcc_assert (head == tail);
 160           return;
 161         }
 162     }
 163   else
 164     {
 165       head = ggc_alloc (sizeof (*head));
 166       head->prev = NULL;
 167       head->next = NULL;
 168       head->stmt = t;
 169       tail = head;
 170     }
 171
 172   TREE_SIDE_EFFECTS (i->container) = 1;
 173
 174   cur = i->ptr;
 175
 176   /* Link it into the list.  */
 177   if (cur)
 178     {
 179       tail->next = cur->next;
 180       if (tail->next)
 181         tail->next->prev = tail;
 182       else
 183         STATEMENT_LIST_TAIL (i->container) = tail;
 184       head->prev = cur;
 185       cur->next = head;
 186     }
 187   else
 188     {
 189       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 190       STATEMENT_LIST_HEAD (i->container) = head;
 191       STATEMENT_LIST_TAIL (i->container) = tail;
 192     }
 193
 194   /* Update the iterator, if requested.  */
 195   switch (mode)
 196     {
 197     case TSI_NEW_STMT:
 198     case TSI_CHAIN_START:
 199       i->ptr = head;
 200       break;
 201     case TSI_CONTINUE_LINKING:
 202     case TSI_CHAIN_END:
 203       i->ptr = tail;
 204       break;
 205     case TSI_SAME_STMT:
 206       gcc_assert (cur);
 207       break;
 208     }
 209 }
 210
 211 /* Remove a stmt from the tree list.  The iterator is updated to point to
 212    the next stmt.  */
 213
 214 void
 215 tsi_delink (tree_stmt_iterator *i)
 216 {
 217   struct tree_statement_list_node *cur, *next, *prev;
 218
 219   cur = i->ptr;
 220   next = cur->next;
 221   prev = cur->prev;
 222
 223   if (prev)
 224     prev->next = next;
 225   else
 226     STATEMENT_LIST_HEAD (i->container) = next;
 227   if (next)
 228     next->prev = prev;
 229   else
 230     STATEMENT_LIST_TAIL (i->container) = prev;
 231
 232   if (!next && !prev)
 233     TREE_SIDE_EFFECTS (i->container) = 0;
 234
 235   i->ptr = next;
 236 }
 237
 238 /* Move all statements in the statement list after I to a new
 239    statement list.  I itself is unchanged.  */
 240
 241 tree
 242 tsi_split_statement_list_after (const tree_stmt_iterator *i)
 243 {
 244   struct tree_statement_list_node *cur, *next;
 245   tree old_sl, new_sl;
 246
 247   cur = i->ptr;
 248   /* How can we possibly split after the end, or before the beginning?  */
 249   gcc_assert (cur);
 250   next = cur->next;
 251
 252   old_sl = i->container;
 253   new_sl = alloc_stmt_list ();
 254   TREE_SIDE_EFFECTS (new_sl) = 1;
 255
 256   STATEMENT_LIST_HEAD (new_sl) = next;
 257   STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
 258   STATEMENT_LIST_TAIL (old_sl) = cur;
 259   cur->next = NULL;
 260   next->prev = NULL;
 261
 262   return new_sl;
 263 }
 264
 265 /* Move all statements in the statement list before I to a new
 266    statement list.  I is set to the head of the new list.  */
 267
 268 tree
 269 tsi_split_statement_list_before (tree_stmt_iterator *i)
 270 {
 271   struct tree_statement_list_node *cur, *prev;
 272   tree old_sl, new_sl;
 273
 274   cur = i->ptr;
 275   /* How can we possibly split after the end, or before the beginning?  */
 276   gcc_assert (cur);
 277   prev = cur->prev;
 278
 279   old_sl = i->container;
 280   new_sl = alloc_stmt_list ();
 281   TREE_SIDE_EFFECTS (new_sl) = 1;
 282   i->container = new_sl;
 283
 284   STATEMENT_LIST_HEAD (new_sl) = cur;
 285   STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
 286   STATEMENT_LIST_TAIL (old_sl) = prev;
 287   cur->prev = NULL;
 288   prev->next = NULL;
 289
 290   return new_sl;
 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   return expr;
 311 }
 312
 313 /* Return the last expression in a sequence of COMPOUND_EXPRs,
 314    or in a STATEMENT_LIST.  */
 315
 316 tree
 317 expr_last (tree expr)
 318 {
 319   if (expr == NULL_TREE)
 320     return expr;
 321
 322   if (TREE_CODE (expr) == STATEMENT_LIST)
 323     {
 324       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 325       return n ? n->stmt : NULL_TREE;
 326     }
 327
 328   while (TREE_CODE (expr) == COMPOUND_EXPR)
 329     expr = TREE_OPERAND (expr, 1);
 330   return expr;
 331 }
 332
 333 /* If EXPR is a single statement, naked or in a STATEMENT_LIST, then
 334    return it.  Otherwise return NULL.  */
 335
 336 tree
 337 expr_only (tree expr)
 338 {
 339   if (expr == NULL_TREE)
 340     return NULL_TREE;
 341
 342   if (TREE_CODE (expr) == STATEMENT_LIST)
 343     {
 344       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 345       if (n && STATEMENT_LIST_HEAD (expr) == n)
 346         return n->stmt;
 347       else
 348         return NULL_TREE;
 349     }
 350
 351   if (TREE_CODE (expr) == COMPOUND_EXPR)
 352     return NULL_TREE;
 353
 354   return expr;
 355 }
 356
 357 #include "gt-tree-iterator.h"