1169689Skan/* Iterator routines for manipulating GENERIC and GIMPLE tree statements. 2169689Skan Copyright (C) 2003, 2004 Free Software Foundation, Inc. 3169689Skan Contributed by Andrew MacLeod <amacleod@redhat.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tree.h" 26169689Skan#include "tree-gimple.h" 27169689Skan#include "tree-iterator.h" 28169689Skan#include "ggc.h" 29169689Skan 30169689Skan 31169689Skan/* This is a cache of STATEMENT_LIST nodes. We create and destroy them 32169689Skan fairly often during gimplification. */ 33169689Skan 34169689Skanstatic GTY ((deletable (""))) tree stmt_list_cache; 35169689Skan 36169689Skantree 37169689Skanalloc_stmt_list (void) 38169689Skan{ 39169689Skan tree list = stmt_list_cache; 40169689Skan if (list) 41169689Skan { 42169689Skan stmt_list_cache = TREE_CHAIN (list); 43169689Skan gcc_assert (stmt_list_cache != list); 44169689Skan memset (list, 0, sizeof(struct tree_common)); 45169689Skan TREE_SET_CODE (list, STATEMENT_LIST); 46169689Skan } 47169689Skan else 48169689Skan list = make_node (STATEMENT_LIST); 49169689Skan TREE_TYPE (list) = void_type_node; 50169689Skan return list; 51169689Skan} 52169689Skan 53169689Skanvoid 54169689Skanfree_stmt_list (tree t) 55169689Skan{ 56169689Skan gcc_assert (!STATEMENT_LIST_HEAD (t)); 57169689Skan gcc_assert (!STATEMENT_LIST_TAIL (t)); 58169689Skan /* If this triggers, it's a sign that the same list is being freed 59169689Skan twice. */ 60169689Skan gcc_assert (t != stmt_list_cache || stmt_list_cache == NULL); 61169689Skan TREE_CHAIN (t) = stmt_list_cache; 62169689Skan stmt_list_cache = t; 63169689Skan} 64169689Skan 65169689Skan/* Links a statement, or a chain of statements, before the current stmt. */ 66169689Skan 67169689Skanvoid 68169689Skantsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode) 69169689Skan{ 70169689Skan struct tree_statement_list_node *head, *tail, *cur; 71169689Skan 72169689Skan /* Die on looping. */ 73169689Skan gcc_assert (t != i->container); 74169689Skan 75169689Skan if (TREE_CODE (t) == STATEMENT_LIST) 76169689Skan { 77169689Skan head = STATEMENT_LIST_HEAD (t); 78169689Skan tail = STATEMENT_LIST_TAIL (t); 79169689Skan STATEMENT_LIST_HEAD (t) = NULL; 80169689Skan STATEMENT_LIST_TAIL (t) = NULL; 81169689Skan 82169689Skan free_stmt_list (t); 83169689Skan 84169689Skan /* Empty statement lists need no work. */ 85169689Skan if (!head || !tail) 86169689Skan { 87169689Skan gcc_assert (head == tail); 88169689Skan return; 89169689Skan } 90169689Skan } 91169689Skan else 92169689Skan { 93169689Skan head = ggc_alloc (sizeof (*head)); 94169689Skan head->prev = NULL; 95169689Skan head->next = NULL; 96169689Skan head->stmt = t; 97169689Skan tail = head; 98169689Skan } 99169689Skan 100169689Skan TREE_SIDE_EFFECTS (i->container) = 1; 101169689Skan 102169689Skan cur = i->ptr; 103169689Skan 104169689Skan /* Link it into the list. */ 105169689Skan if (cur) 106169689Skan { 107169689Skan head->prev = cur->prev; 108169689Skan if (head->prev) 109169689Skan head->prev->next = head; 110169689Skan else 111169689Skan STATEMENT_LIST_HEAD (i->container) = head; 112169689Skan tail->next = cur; 113169689Skan cur->prev = tail; 114169689Skan } 115169689Skan else 116169689Skan { 117169689Skan head->prev = STATEMENT_LIST_TAIL (i->container); 118169689Skan if (head->prev) 119169689Skan head->prev->next = head; 120169689Skan else 121169689Skan STATEMENT_LIST_HEAD (i->container) = head; 122169689Skan STATEMENT_LIST_TAIL (i->container) = tail; 123169689Skan } 124169689Skan 125169689Skan /* Update the iterator, if requested. */ 126169689Skan switch (mode) 127169689Skan { 128169689Skan case TSI_NEW_STMT: 129169689Skan case TSI_CONTINUE_LINKING: 130169689Skan case TSI_CHAIN_START: 131169689Skan i->ptr = head; 132169689Skan break; 133169689Skan case TSI_CHAIN_END: 134169689Skan i->ptr = tail; 135169689Skan break; 136169689Skan case TSI_SAME_STMT: 137169689Skan break; 138169689Skan } 139169689Skan} 140169689Skan 141169689Skan/* Links a statement, or a chain of statements, after the current stmt. */ 142169689Skan 143169689Skanvoid 144169689Skantsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode) 145169689Skan{ 146169689Skan struct tree_statement_list_node *head, *tail, *cur; 147169689Skan 148169689Skan /* Die on looping. */ 149169689Skan gcc_assert (t != i->container); 150169689Skan 151169689Skan if (TREE_CODE (t) == STATEMENT_LIST) 152169689Skan { 153169689Skan head = STATEMENT_LIST_HEAD (t); 154169689Skan tail = STATEMENT_LIST_TAIL (t); 155169689Skan STATEMENT_LIST_HEAD (t) = NULL; 156169689Skan STATEMENT_LIST_TAIL (t) = NULL; 157169689Skan 158169689Skan free_stmt_list (t); 159169689Skan 160169689Skan /* Empty statement lists need no work. */ 161169689Skan if (!head || !tail) 162169689Skan { 163169689Skan gcc_assert (head == tail); 164169689Skan return; 165169689Skan } 166169689Skan } 167169689Skan else 168169689Skan { 169169689Skan head = ggc_alloc (sizeof (*head)); 170169689Skan head->prev = NULL; 171169689Skan head->next = NULL; 172169689Skan head->stmt = t; 173169689Skan tail = head; 174169689Skan } 175169689Skan 176169689Skan TREE_SIDE_EFFECTS (i->container) = 1; 177169689Skan 178169689Skan cur = i->ptr; 179169689Skan 180169689Skan /* Link it into the list. */ 181169689Skan if (cur) 182169689Skan { 183169689Skan tail->next = cur->next; 184169689Skan if (tail->next) 185169689Skan tail->next->prev = tail; 186169689Skan else 187169689Skan STATEMENT_LIST_TAIL (i->container) = tail; 188169689Skan head->prev = cur; 189169689Skan cur->next = head; 190169689Skan } 191169689Skan else 192169689Skan { 193169689Skan gcc_assert (!STATEMENT_LIST_TAIL (i->container)); 194169689Skan STATEMENT_LIST_HEAD (i->container) = head; 195169689Skan STATEMENT_LIST_TAIL (i->container) = tail; 196169689Skan } 197169689Skan 198169689Skan /* Update the iterator, if requested. */ 199169689Skan switch (mode) 200169689Skan { 201169689Skan case TSI_NEW_STMT: 202169689Skan case TSI_CHAIN_START: 203169689Skan i->ptr = head; 204169689Skan break; 205169689Skan case TSI_CONTINUE_LINKING: 206169689Skan case TSI_CHAIN_END: 207169689Skan i->ptr = tail; 208169689Skan break; 209169689Skan case TSI_SAME_STMT: 210169689Skan gcc_assert (cur); 211169689Skan break; 212169689Skan } 213169689Skan} 214169689Skan 215169689Skan/* Remove a stmt from the tree list. The iterator is updated to point to 216169689Skan the next stmt. */ 217169689Skan 218169689Skanvoid 219169689Skantsi_delink (tree_stmt_iterator *i) 220169689Skan{ 221169689Skan struct tree_statement_list_node *cur, *next, *prev; 222169689Skan 223169689Skan cur = i->ptr; 224169689Skan next = cur->next; 225169689Skan prev = cur->prev; 226169689Skan 227169689Skan if (prev) 228169689Skan prev->next = next; 229169689Skan else 230169689Skan STATEMENT_LIST_HEAD (i->container) = next; 231169689Skan if (next) 232169689Skan next->prev = prev; 233169689Skan else 234169689Skan STATEMENT_LIST_TAIL (i->container) = prev; 235169689Skan 236169689Skan if (!next && !prev) 237169689Skan TREE_SIDE_EFFECTS (i->container) = 0; 238169689Skan 239169689Skan i->ptr = next; 240169689Skan} 241169689Skan 242169689Skan/* Move all statements in the statement list after I to a new 243169689Skan statement list. I itself is unchanged. */ 244169689Skan 245169689Skantree 246169689Skantsi_split_statement_list_after (const tree_stmt_iterator *i) 247169689Skan{ 248169689Skan struct tree_statement_list_node *cur, *next; 249169689Skan tree old_sl, new_sl; 250169689Skan 251169689Skan cur = i->ptr; 252169689Skan /* How can we possibly split after the end, or before the beginning? */ 253169689Skan gcc_assert (cur); 254169689Skan next = cur->next; 255169689Skan 256169689Skan old_sl = i->container; 257169689Skan new_sl = alloc_stmt_list (); 258169689Skan TREE_SIDE_EFFECTS (new_sl) = 1; 259169689Skan 260169689Skan STATEMENT_LIST_HEAD (new_sl) = next; 261169689Skan STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl); 262169689Skan STATEMENT_LIST_TAIL (old_sl) = cur; 263169689Skan cur->next = NULL; 264169689Skan next->prev = NULL; 265169689Skan 266169689Skan return new_sl; 267169689Skan} 268169689Skan 269169689Skan/* Move all statements in the statement list before I to a new 270169689Skan statement list. I is set to the head of the new list. */ 271169689Skan 272169689Skantree 273169689Skantsi_split_statement_list_before (tree_stmt_iterator *i) 274169689Skan{ 275169689Skan struct tree_statement_list_node *cur, *prev; 276169689Skan tree old_sl, new_sl; 277169689Skan 278169689Skan cur = i->ptr; 279169689Skan /* How can we possibly split after the end, or before the beginning? */ 280169689Skan gcc_assert (cur); 281169689Skan prev = cur->prev; 282169689Skan 283169689Skan old_sl = i->container; 284169689Skan new_sl = alloc_stmt_list (); 285169689Skan TREE_SIDE_EFFECTS (new_sl) = 1; 286169689Skan i->container = new_sl; 287169689Skan 288169689Skan STATEMENT_LIST_HEAD (new_sl) = cur; 289169689Skan STATEMENT_LIST_TAIL (new_sl) = STATEMENT_LIST_TAIL (old_sl); 290169689Skan STATEMENT_LIST_TAIL (old_sl) = prev; 291169689Skan cur->prev = NULL; 292169689Skan if (prev) 293169689Skan prev->next = NULL; 294169689Skan 295169689Skan return new_sl; 296169689Skan} 297169689Skan 298169689Skan/* Return the first expression in a sequence of COMPOUND_EXPRs, 299169689Skan or in a STATEMENT_LIST. */ 300169689Skan 301169689Skantree 302169689Skanexpr_first (tree expr) 303169689Skan{ 304169689Skan if (expr == NULL_TREE) 305169689Skan return expr; 306169689Skan 307169689Skan if (TREE_CODE (expr) == STATEMENT_LIST) 308169689Skan { 309169689Skan struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr); 310169689Skan return n ? n->stmt : NULL_TREE; 311169689Skan } 312169689Skan 313169689Skan while (TREE_CODE (expr) == COMPOUND_EXPR) 314169689Skan expr = TREE_OPERAND (expr, 0); 315169689Skan return expr; 316169689Skan} 317169689Skan 318169689Skan/* Return the last expression in a sequence of COMPOUND_EXPRs, 319169689Skan or in a STATEMENT_LIST. */ 320169689Skan 321169689Skantree 322169689Skanexpr_last (tree expr) 323169689Skan{ 324169689Skan if (expr == NULL_TREE) 325169689Skan return expr; 326169689Skan 327169689Skan if (TREE_CODE (expr) == STATEMENT_LIST) 328169689Skan { 329169689Skan struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr); 330169689Skan return n ? n->stmt : NULL_TREE; 331169689Skan } 332169689Skan 333169689Skan while (TREE_CODE (expr) == COMPOUND_EXPR) 334169689Skan expr = TREE_OPERAND (expr, 1); 335169689Skan return expr; 336169689Skan} 337169689Skan 338169689Skan/* If EXPR is a single statement return it. If EXPR is a 339169689Skan STATEMENT_LIST containing exactly one statement S, return S. 340169689Skan Otherwise, return NULL. */ 341169689Skan 342169689Skantree 343169689Skanexpr_only (tree expr) 344169689Skan{ 345169689Skan if (expr == NULL_TREE) 346169689Skan return NULL_TREE; 347169689Skan 348169689Skan if (TREE_CODE (expr) == STATEMENT_LIST) 349169689Skan { 350169689Skan struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr); 351169689Skan if (n && STATEMENT_LIST_HEAD (expr) == n) 352169689Skan return n->stmt; 353169689Skan else 354169689Skan return NULL_TREE; 355169689Skan } 356169689Skan 357169689Skan if (TREE_CODE (expr) == COMPOUND_EXPR) 358169689Skan return NULL_TREE; 359169689Skan 360169689Skan return expr; 361169689Skan} 362169689Skan 363169689Skan#include "gt-tree-iterator.h" 364