gcc/tree-iterator.c

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