1/* Iterator routines for manipulating GENERIC and GIMPLE tree statements. 2 Copyright (C) 2003-2015 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 3, 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 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 "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "options.h" 32#include "wide-int.h" 33#include "inchash.h" 34#include "tree.h" 35#include "tree-iterator.h" 36#include "ggc.h" 37 38 39/* This is a cache of STATEMENT_LIST nodes. We create and destroy them 40 fairly often during gimplification. */ 41 42static GTY ((deletable (""))) vec<tree, va_gc> *stmt_list_cache; 43 44tree 45alloc_stmt_list (void) 46{ 47 tree list; 48 if (!vec_safe_is_empty (stmt_list_cache)) 49 { 50 list = stmt_list_cache->pop (); 51 memset (list, 0, sizeof (struct tree_base)); 52 TREE_SET_CODE (list, STATEMENT_LIST); 53 } 54 else 55 list = make_node (STATEMENT_LIST); 56 TREE_TYPE (list) = void_type_node; 57 return list; 58} 59 60void 61free_stmt_list (tree t) 62{ 63 gcc_assert (!STATEMENT_LIST_HEAD (t)); 64 gcc_assert (!STATEMENT_LIST_TAIL (t)); 65 vec_safe_push (stmt_list_cache, t); 66} 67 68/* A subroutine of append_to_statement_list{,_force}. T is not NULL. */ 69 70static void 71append_to_statement_list_1 (tree t, tree *list_p) 72{ 73 tree list = *list_p; 74 tree_stmt_iterator i; 75 76 if (!list) 77 { 78 if (t && TREE_CODE (t) == STATEMENT_LIST) 79 { 80 *list_p = t; 81 return; 82 } 83 *list_p = list = alloc_stmt_list (); 84 } 85 else if (TREE_CODE (list) != STATEMENT_LIST) 86 { 87 tree first = list; 88 *list_p = list = alloc_stmt_list (); 89 i = tsi_last (list); 90 tsi_link_after (&i, first, TSI_CONTINUE_LINKING); 91 } 92 93 i = tsi_last (list); 94 tsi_link_after (&i, t, TSI_CONTINUE_LINKING); 95} 96 97/* Add T to the end of the list container pointed to by LIST_P. 98 If T is an expression with no effects, it is ignored. */ 99 100void 101append_to_statement_list (tree t, tree *list_p) 102{ 103 if (t && TREE_SIDE_EFFECTS (t)) 104 append_to_statement_list_1 (t, list_p); 105} 106 107/* Similar, but the statement is always added, regardless of side effects. */ 108 109void 110append_to_statement_list_force (tree t, tree *list_p) 111{ 112 if (t != NULL_TREE) 113 append_to_statement_list_1 (t, list_p); 114} 115 116/* Links a statement, or a chain of statements, before the current stmt. */ 117 118void 119tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode) 120{ 121 struct tree_statement_list_node *head, *tail, *cur; 122 123 /* Die on looping. */ 124 gcc_assert (t != i->container); 125 126 if (TREE_CODE (t) == STATEMENT_LIST) 127 { 128 head = STATEMENT_LIST_HEAD (t); 129 tail = STATEMENT_LIST_TAIL (t); 130 STATEMENT_LIST_HEAD (t) = NULL; 131 STATEMENT_LIST_TAIL (t) = NULL; 132 133 free_stmt_list (t); 134 135 /* Empty statement lists need no work. */ 136 if (!head || !tail) 137 { 138 gcc_assert (head == tail); 139 return; 140 } 141 } 142 else 143 { 144 head = ggc_alloc<tree_statement_list_node> (); 145 head->prev = NULL; 146 head->next = NULL; 147 head->stmt = t; 148 tail = head; 149 } 150 151 TREE_SIDE_EFFECTS (i->container) = 1; 152 153 cur = i->ptr; 154 155 /* Link it into the list. */ 156 if (cur) 157 { 158 head->prev = cur->prev; 159 if (head->prev) 160 head->prev->next = head; 161 else 162 STATEMENT_LIST_HEAD (i->container) = head; 163 tail->next = cur; 164 cur->prev = tail; 165 } 166 else 167 { 168 head->prev = STATEMENT_LIST_TAIL (i->container); 169 if (head->prev) 170 head->prev->next = head; 171 else 172 STATEMENT_LIST_HEAD (i->container) = head; 173 STATEMENT_LIST_TAIL (i->container) = tail; 174 } 175 176 /* Update the iterator, if requested. */ 177 switch (mode) 178 { 179 case TSI_NEW_STMT: 180 case TSI_CONTINUE_LINKING: 181 case TSI_CHAIN_START: 182 i->ptr = head; 183 break; 184 case TSI_CHAIN_END: 185 i->ptr = tail; 186 break; 187 case TSI_SAME_STMT: 188 break; 189 } 190} 191 192/* Links a statement, or a chain of statements, after the current stmt. */ 193 194void 195tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode) 196{ 197 struct tree_statement_list_node *head, *tail, *cur; 198 199 /* Die on looping. */ 200 gcc_assert (t != i->container); 201 202 if (TREE_CODE (t) == STATEMENT_LIST) 203 { 204 head = STATEMENT_LIST_HEAD (t); 205 tail = STATEMENT_LIST_TAIL (t); 206 STATEMENT_LIST_HEAD (t) = NULL; 207 STATEMENT_LIST_TAIL (t) = NULL; 208 209 free_stmt_list (t); 210 211 /* Empty statement lists need no work. */ 212 if (!head || !tail) 213 { 214 gcc_assert (head == tail); 215 return; 216 } 217 } 218 else 219 { 220 head = ggc_alloc<tree_statement_list_node> (); 221 head->prev = NULL; 222 head->next = NULL; 223 head->stmt = t; 224 tail = head; 225 } 226 227 TREE_SIDE_EFFECTS (i->container) = 1; 228 229 cur = i->ptr; 230 231 /* Link it into the list. */ 232 if (cur) 233 { 234 tail->next = cur->next; 235 if (tail->next) 236 tail->next->prev = tail; 237 else 238 STATEMENT_LIST_TAIL (i->container) = tail; 239 head->prev = cur; 240 cur->next = head; 241 } 242 else 243 { 244 gcc_assert (!STATEMENT_LIST_TAIL (i->container)); 245 STATEMENT_LIST_HEAD (i->container) = head; 246 STATEMENT_LIST_TAIL (i->container) = tail; 247 } 248 249 /* Update the iterator, if requested. */ 250 switch (mode) 251 { 252 case TSI_NEW_STMT: 253 case TSI_CHAIN_START: 254 i->ptr = head; 255 break; 256 case TSI_CONTINUE_LINKING: 257 case TSI_CHAIN_END: 258 i->ptr = tail; 259 break; 260 case TSI_SAME_STMT: 261 gcc_assert (cur); 262 break; 263 } 264} 265 266/* Remove a stmt from the tree list. The iterator is updated to point to 267 the next stmt. */ 268 269void 270tsi_delink (tree_stmt_iterator *i) 271{ 272 struct tree_statement_list_node *cur, *next, *prev; 273 274 cur = i->ptr; 275 next = cur->next; 276 prev = cur->prev; 277 278 if (prev) 279 prev->next = next; 280 else 281 STATEMENT_LIST_HEAD (i->container) = next; 282 if (next) 283 next->prev = prev; 284 else 285 STATEMENT_LIST_TAIL (i->container) = prev; 286 287 if (!next && !prev) 288 TREE_SIDE_EFFECTS (i->container) = 0; 289 290 i->ptr = next; 291} 292 293/* Return the first expression in a sequence of COMPOUND_EXPRs, 294 or in a STATEMENT_LIST. */ 295 296tree 297expr_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 311 return expr; 312} 313 314/* Return the last expression in a sequence of COMPOUND_EXPRs, 315 or in a STATEMENT_LIST. */ 316 317tree 318expr_last (tree expr) 319{ 320 if (expr == NULL_TREE) 321 return expr; 322 323 if (TREE_CODE (expr) == STATEMENT_LIST) 324 { 325 struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr); 326 return n ? n->stmt : NULL_TREE; 327 } 328 329 while (TREE_CODE (expr) == COMPOUND_EXPR) 330 expr = TREE_OPERAND (expr, 1); 331 332 return expr; 333} 334 335#include "gt-tree-iterator.h" 336