gcc/lists.c

   1 /* List management for the GCC expander.
   2    Copyright (C) 1987-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along 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
  28 static 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.  */
  33 static GTY ((deletable)) rtx unused_insn_list;
  34
  35 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused.  */
  36 static 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.  */
  42 static void
  43 free_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.  */
  69 static rtx *
  70 find_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.  */
  78 static void
  79 remove_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.  */
  90 rtx
  91 remove_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.  */
 104 rtx_insn_list *
 105 alloc_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.  */
 128 rtx_expr_list *
 129 alloc_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.  */
 148 void
 149 free_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.  */
 157 void
 158 free_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.  */
 166 rtx_insn_list *
 167 copy_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.  */
 184 rtx_insn_list *
 185 concat_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.  */
 197 void
 198 free_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.  */
 205 void
 206 free_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.  */
 215 void
 216 remove_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.  */
 222 rtx_insn *
 223 remove_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.  */
 235 rtx
 236 remove_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"