tree-iterator.c revision 169690
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 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, 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 34static GTY ((deletable (""))) tree stmt_list_cache; 35 36tree 37alloc_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 53void 54free_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 67void 68tsi_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 143void 144tsi_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 218void 219tsi_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 245tree 246tsi_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 272tree 273tsi_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 295 return new_sl; 296} 297 298/* Return the first expression in a sequence of COMPOUND_EXPRs, 299 or in a STATEMENT_LIST. */ 300 301tree 302expr_first (tree expr) 303{ 304 if (expr == NULL_TREE) 305 return expr; 306 307 if (TREE_CODE (expr) == STATEMENT_LIST) 308 { 309 struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr); 310 return n ? n->stmt : NULL_TREE; 311 } 312 313 while (TREE_CODE (expr) == COMPOUND_EXPR) 314 expr = TREE_OPERAND (expr, 0); 315 return expr; 316} 317 318/* Return the last expression in a sequence of COMPOUND_EXPRs, 319 or in a STATEMENT_LIST. */ 320 321tree 322expr_last (tree expr) 323{ 324 if (expr == NULL_TREE) 325 return expr; 326 327 if (TREE_CODE (expr) == STATEMENT_LIST) 328 { 329 struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr); 330 return n ? n->stmt : NULL_TREE; 331 } 332 333 while (TREE_CODE (expr) == COMPOUND_EXPR) 334 expr = TREE_OPERAND (expr, 1); 335 return expr; 336} 337 338/* If EXPR is a single statement return it. If EXPR is a 339 STATEMENT_LIST containing exactly one statement S, return S. 340 Otherwise, return NULL. */ 341 342tree 343expr_only (tree expr) 344{ 345 if (expr == NULL_TREE) 346 return NULL_TREE; 347 348 if (TREE_CODE (expr) == STATEMENT_LIST) 349 { 350 struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr); 351 if (n && STATEMENT_LIST_HEAD (expr) == n) 352 return n->stmt; 353 else 354 return NULL_TREE; 355 } 356 357 if (TREE_CODE (expr) == COMPOUND_EXPR) 358 return NULL_TREE; 359 360 return expr; 361} 362 363#include "gt-tree-iterator.h" 364