1/* List management for the GCC expander.
2   Copyright (C) 1987-2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "tm.h"
24#include "diagnostic-core.h"
25#include "rtl.h"
26#include "ggc.h"
27
28static void free_list (rtx *, rtx *);
29
30/* Functions for maintaining cache-able lists of EXPR_LIST and INSN_LISTs.  */
31
32/* An INSN_LIST containing all INSN_LISTs allocated but currently unused.  */
33static GTY ((deletable)) rtx unused_insn_list;
34
35/* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused.  */
36static GTY ((deletable)) rtx unused_expr_list;
37
38/* This function will free an entire list of either EXPR_LIST, INSN_LIST
39   or DEPS_LIST nodes.  This is to be used only on lists that consist
40   exclusively of nodes of one type only.  This is only called by
41   free_EXPR_LIST_list, free_INSN_LIST_list and free_DEPS_LIST_list.  */
42static void
43free_list (rtx *listp, rtx *unused_listp)
44{
45  rtx link, prev_link;
46
47  prev_link = *listp;
48  link = XEXP (prev_link, 1);
49
50  gcc_assert (unused_listp != &unused_insn_list
51	      || GET_CODE (prev_link) == INSN_LIST);
52
53  while (link)
54    {
55      gcc_assert (unused_listp != &unused_insn_list
56		  || GET_CODE (prev_link) == INSN_LIST);
57
58      prev_link = link;
59      link = XEXP (link, 1);
60    }
61
62  XEXP (prev_link, 1) = *unused_listp;
63  *unused_listp = *listp;
64  *listp = 0;
65}
66
67/* Find corresponding to ELEM node in the list pointed to by LISTP.
68   This node must exist in the list.  Returns pointer to that node.  */
69static rtx *
70find_list_elem (rtx elem, rtx *listp)
71{
72  while (XEXP (*listp, 0) != elem)
73    listp = &XEXP (*listp, 1);
74  return listp;
75}
76
77/* Remove the node pointed to by LISTP from the list.  */
78static void
79remove_list_node (rtx *listp)
80{
81  rtx node;
82
83  node = *listp;
84  *listp = XEXP (node, 1);
85  XEXP (node, 1) = 0;
86}
87
88/* Removes corresponding to ELEM node from the list pointed to by LISTP.
89   Returns that node.  */
90rtx
91remove_list_elem (rtx elem, rtx *listp)
92{
93  rtx node;
94
95  listp = find_list_elem (elem, listp);
96  node = *listp;
97  remove_list_node (listp);
98  return node;
99}
100
101/* This call is used in place of a gen_rtx_INSN_LIST. If there is a cached
102   node available, we'll use it, otherwise a call to gen_rtx_INSN_LIST
103   is made.  */
104rtx_insn_list *
105alloc_INSN_LIST (rtx val, rtx next)
106{
107  rtx_insn_list *r;
108
109  if (unused_insn_list)
110    {
111      r = as_a <rtx_insn_list *> (unused_insn_list);
112      unused_insn_list = r->next ();
113      XEXP (r, 0) = val;
114      XEXP (r, 1) = next;
115      PUT_REG_NOTE_KIND (r, VOIDmode);
116
117      gcc_assert (GET_CODE (r) == INSN_LIST);
118    }
119  else
120    r = gen_rtx_INSN_LIST (VOIDmode, val, next);
121
122  return r;
123}
124
125/* This call is used in place of a gen_rtx_EXPR_LIST. If there is a cached
126   node available, we'll use it, otherwise a call to gen_rtx_EXPR_LIST
127   is made.  */
128rtx_expr_list *
129alloc_EXPR_LIST (int kind, rtx val, rtx next)
130{
131  rtx_expr_list *r;
132
133  if (unused_expr_list)
134    {
135      r = as_a <rtx_expr_list *> (unused_expr_list);
136      unused_expr_list = XEXP (r, 1);
137      XEXP (r, 0) = val;
138      XEXP (r, 1) = next;
139      PUT_REG_NOTE_KIND (r, kind);
140    }
141  else
142    r = gen_rtx_EXPR_LIST ((machine_mode) kind, val, next);
143
144  return r;
145}
146
147/* This function will free up an entire list of EXPR_LIST nodes.  */
148void
149free_EXPR_LIST_list (rtx_expr_list **listp)
150{
151  if (*listp == 0)
152    return;
153  free_list ((rtx *)listp, &unused_expr_list);
154}
155
156/* This function will free up an entire list of INSN_LIST nodes.  */
157void
158free_INSN_LIST_list (rtx_insn_list **listp)
159{
160  if (*listp == 0)
161    return;
162  free_list ((rtx *)listp, &unused_insn_list);
163}
164
165/* Make a copy of the INSN_LIST list LINK and return it.  */
166rtx_insn_list *
167copy_INSN_LIST (rtx_insn_list *link)
168{
169  rtx_insn_list *new_queue;
170  rtx_insn_list **pqueue = &new_queue;
171
172  for (; link; link = link->next ())
173    {
174      rtx_insn *x = link->insn ();
175      rtx_insn_list *newlink = alloc_INSN_LIST (x, NULL);
176      *pqueue = newlink;
177      pqueue = (rtx_insn_list **)&XEXP (newlink, 1);
178    }
179  *pqueue = NULL;
180  return new_queue;
181}
182
183/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
184rtx_insn_list *
185concat_INSN_LIST (rtx_insn_list *copy, rtx_insn_list *old)
186{
187  rtx_insn_list *new_rtx = old;
188  for (; copy ; copy = copy->next ())
189    {
190      new_rtx = alloc_INSN_LIST (copy->insn (), new_rtx);
191      PUT_REG_NOTE_KIND (new_rtx, REG_NOTE_KIND (copy));
192    }
193  return new_rtx;
194}
195
196/* This function will free up an individual EXPR_LIST node.  */
197void
198free_EXPR_LIST_node (rtx ptr)
199{
200  XEXP (ptr, 1) = unused_expr_list;
201  unused_expr_list = ptr;
202}
203
204/* This function will free up an individual INSN_LIST node.  */
205void
206free_INSN_LIST_node (rtx ptr)
207{
208  gcc_assert (GET_CODE (ptr) == INSN_LIST);
209  XEXP (ptr, 1) = unused_insn_list;
210  unused_insn_list = ptr;
211}
212
213/* Remove and free corresponding to ELEM node in the INSN_LIST pointed to
214   by LISTP.  */
215void
216remove_free_INSN_LIST_elem (rtx_insn *elem, rtx_insn_list **listp)
217{
218  free_INSN_LIST_node (remove_list_elem (elem, (rtx *)listp));
219}
220
221/* Remove and free the first node in the INSN_LIST pointed to by LISTP.  */
222rtx_insn *
223remove_free_INSN_LIST_node (rtx_insn_list **listp)
224{
225  rtx_insn_list *node = *listp;
226  rtx_insn *elem = node->insn ();
227
228  remove_list_node ((rtx *)listp);
229  free_INSN_LIST_node (node);
230
231  return elem;
232}
233
234/* Remove and free the first node in the EXPR_LIST pointed to by LISTP.  */
235rtx
236remove_free_EXPR_LIST_node (rtx_expr_list **listp)
237{
238  rtx_expr_list *node = *listp;
239  rtx elem = XEXP (node, 0);
240
241  remove_list_node ((rtx *)listp);
242  free_EXPR_LIST_node (node);
243
244  return elem;
245}
246
247#include "gt-lists.h"
248