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       gcc_assert (stmt_list_cache != list);
  44       memset (list, 0, sizeof(struct tree_common));
  45       TREE_SET_CODE (list, STATEMENT_LIST);
  46     }
  47   else
  48     list = make_node (STATEMENT_LIST);
  49   TREE_TYPE (list) = void_type_node;
  50   return list;
  51 }
  52
  53 void
  54 free_stmt_list (tree t)
  55 {
  56   gcc_assert (!STATEMENT_LIST_HEAD (t));
  57   gcc_assert (!STATEMENT_LIST_TAIL (t));
  58   /* If this triggers, it's a sign that the same list is being freed
  59      twice.  */
  60   gcc_assert (t != stmt_list_cache || stmt_list_cache == NULL);
  61   TREE_CHAIN (t) = stmt_list_cache;
  62   stmt_list_cache = t;
  63 }
  64
  65 /* Links a statement, or a chain of statements, before the current stmt.  */
  66
  67 void
  68 tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
  69 {
  70   struct tree_statement_list_node *head, *tail, *cur;
  71
  72   /* Die on looping.  */
  73   gcc_assert (t != i->container);
  74
  75   if (TREE_CODE (t) == STATEMENT_LIST)
  76     {
  77       head = STATEMENT_LIST_HEAD (t);
  78       tail = STATEMENT_LIST_TAIL (t);
  79       STATEMENT_LIST_HEAD (t) = NULL;
  80       STATEMENT_LIST_TAIL (t) = NULL;
  81
  82       free_stmt_list (t);
  83
  84       /* Empty statement lists need no work.  */
  85       if (!head || !tail)
  86         {
  87           gcc_assert (head == tail);
  88           return;
  89         }
  90     }
  91   else
  92     {
  93       head = ggc_alloc (sizeof (*head));
  94       head->prev = NULL;
  95       head->next = NULL;
  96       head->stmt = t;
  97       tail = head;
  98     }
  99
 100   TREE_SIDE_EFFECTS (i->container) = 1;
 101
 102   cur = i->ptr;
 103
 104   /* Link it into the list.  */
 105   if (cur)
 106     {
 107       head->prev = cur->prev;
 108       if (head->prev)
 109         head->prev->next = head;
 110       else
 111         STATEMENT_LIST_HEAD (i->container) = head;
 112       tail->next = cur;
 113       cur->prev = tail;
 114     }
 115   else
 116     {
 117       head->prev = STATEMENT_LIST_TAIL (i->container);
 118       if (head->prev)
 119        head->prev->next = head;
 120       else
 121        STATEMENT_LIST_HEAD (i->container) = head;
 122       STATEMENT_LIST_TAIL (i->container) = tail;
 123     }
 124
 125   /* Update the iterator, if requested.  */
 126   switch (mode)
 127     {
 128     case TSI_NEW_STMT:
 129     case TSI_CONTINUE_LINKING:
 130     case TSI_CHAIN_START:
 131       i->ptr = head;
 132       break;
 133     case TSI_CHAIN_END:
 134       i->ptr = tail;
 135       break;
 136     case TSI_SAME_STMT:
 137       break;
 138     }
 139 }
 140
 141 /* Links a statement, or a chain of statements, after the current stmt.  */
 142
 143 void
 144 tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
 145 {
 146   struct tree_statement_list_node *head, *tail, *cur;
 147
 148   /* Die on looping.  */
 149   gcc_assert (t != i->container);
 150
 151   if (TREE_CODE (t) == STATEMENT_LIST)
 152     {
 153       head = STATEMENT_LIST_HEAD (t);
 154       tail = STATEMENT_LIST_TAIL (t);
 155       STATEMENT_LIST_HEAD (t) = NULL;
 156       STATEMENT_LIST_TAIL (t) = NULL;
 157
 158       free_stmt_list (t);
 159
 160       /* Empty statement lists need no work.  */
 161       if (!head || !tail)
 162         {
 163           gcc_assert (head == tail);
 164           return;
 165         }
 166     }
 167   else
 168     {
 169       head = ggc_alloc (sizeof (*head));
 170       head->prev = NULL;
 171       head->next = NULL;
 172       head->stmt = t;
 173       tail = head;
 174     }
 175
 176   TREE_SIDE_EFFECTS (i->container) = 1;
 177
 178   cur = i->ptr;
 179
 180   /* Link it into the list.  */
 181   if (cur)
 182     {
 183       tail->next = cur->next;
 184       if (tail->next)
 185         tail->next->prev = tail;
 186       else
 187         STATEMENT_LIST_TAIL (i->container) = tail;
 188       head->prev = cur;
 189       cur->next = head;
 190     }
 191   else
 192     {
 193       gcc_assert (!STATEMENT_LIST_TAIL (i->container));
 194       STATEMENT_LIST_HEAD (i->container) = head;
 195       STATEMENT_LIST_TAIL (i->container) = tail;
 196     }
 197
 198   /* Update the iterator, if requested.  */
 199   switch (mode)
 200     {
 201     case TSI_NEW_STMT:
 202     case TSI_CHAIN_START:
 203       i->ptr = head;
 204       break;
 205     case TSI_CONTINUE_LINKING:
 206     case TSI_CHAIN_END:
 207       i->ptr = tail;
 208       break;
 209     case TSI_SAME_STMT:
 210       gcc_assert (cur);
 211       break;
 212     }
 213 }
 214
 215 /* Remove a stmt from the tree list.  The iterator is updated to point to
 216    the next stmt.  */
 217
 218 void
 219 tsi_delink (tree_stmt_iterator *i)
 220 {
 221   struct tree_statement_list_node *cur, *next, *prev;
 222
 223   cur = i->ptr;
 224   next = cur->next;
 225   prev = cur->prev;
 226
 227   if (prev)
 228     prev->next = next;
 229   else
 230     STATEMENT_LIST_HEAD (i->container) = next;
 231   if (next)
 232     next->prev = prev;
 233   else
 234     STATEMENT_LIST_TAIL (i->container) = prev;
 235
 236   if (!next && !prev)
 237     TREE_SIDE_EFFECTS (i->container) = 0;
 238
 239   i->ptr = next;
 240 }
 241
 242 /* Move all statements in the statement list after I to a new
 243    statement list.  I itself is unchanged.  */
 244
 245 tree
 246 tsi_split_statement_list_after (const tree_stmt_iterator *i)
 247 {
 248   struct tree_statement_list_node *cur, *next;
 249   tree old_sl, new_sl;
 250
 251   cur = i->ptr;
 252   /* How can we possibly split after the end, or before the beginning?  */
 253   gcc_assert (cur);
 254   next = cur->next;
 255
 256   old_sl = i->container;
 257   new_sl = alloc_stmt_list ();
 258   TREE_SIDE_EFFECTS (new_sl) = 1;
 259
 260   STATEMENT_LIST_HEAD (new_sl) = next;
 261   STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
 262   STATEMENT_LIST_TAIL (old_sl) = cur;
 263   cur->next = NULL;
 264   next->prev = NULL;
 265
 266   return new_sl;
 267 }
 268
 269 /* Move all statements in the statement list before I to a new
 270    statement list.  I is set to the head of the new list.  */
 271
 272 tree
 273 tsi_split_statement_list_before (tree_stmt_iterator *i)
 274 {
 275   struct tree_statement_list_node *cur, *prev;
 276   tree old_sl, new_sl;
 277
 278   cur = i->ptr;
 279   /* How can we possibly split after the end, or before the beginning?  */
 280   gcc_assert (cur);
 281   prev = cur->prev;
 282
 283   old_sl = i->container;
 284   new_sl = alloc_stmt_list ();
 285   TREE_SIDE_EFFECTS (new_sl) = 1;
 286   i->container = new_sl;
 287
 288   STATEMENT_LIST_HEAD (new_sl) = cur;
 289   STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl);
 290   STATEMENT_LIST_TAIL (old_sl) = prev;
 291   cur->prev = NULL;
 292   if (prev)
 293     prev->next = NULL;
 294   else
 295     STATEMENT_LIST_HEAD (old_sl) = NULL;
 296
 297   return new_sl;
 298 }
 299
 300 /* Return the first expression in a sequence of COMPOUND_EXPRs,
 301    or in a STATEMENT_LIST.  */
 302
 303 tree
 304 expr_first (tree expr)
 305 {
 306   if (expr == NULL_TREE)
 307     return expr;
 308
 309   if (TREE_CODE (expr) == STATEMENT_LIST)
 310     {
 311       struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
 312       return n ? n->stmt : NULL_TREE;
 313     }
 314
 315   while (TREE_CODE (expr) == COMPOUND_EXPR)
 316     expr = TREE_OPERAND (expr, 0);
 317   return expr;
 318 }
 319
 320 /* Return the last expression in a sequence of COMPOUND_EXPRs,
 321    or in a STATEMENT_LIST.  */
 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       return n ? n->stmt : NULL_TREE;
 333     }
 334
 335   while (TREE_CODE (expr) == COMPOUND_EXPR)
 336     expr = TREE_OPERAND (expr, 1);
 337   return expr;
 338 }
 339
 340 /* If EXPR is a single statement return it.  If EXPR is a
 341    STATEMENT_LIST containing exactly one statement S, return S.
 342    Otherwise, return NULL.  */
 343
 344 tree
 345 expr_only (tree expr)
 346 {
 347   if (expr == NULL_TREE)
 348     return NULL_TREE;
 349
 350   if (TREE_CODE (expr) == STATEMENT_LIST)
 351     {
 352       struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
 353       if (n && STATEMENT_LIST_HEAD (expr) == n)
 354         return n->stmt;
 355       else
 356         return NULL_TREE;
 357     }
 358
 359   if (TREE_CODE (expr) == COMPOUND_EXPR)
 360     return NULL_TREE;
 361
 362   return expr;
 363 }
 364
 365 #include "gt-tree-iterator.h"