1/* Shared code for before and after reload gcse implementations.
2   Copyright (C) 1997-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   It is expected that more hunks of gcse.c and postreload-gcse.c should
21   migrate into this file.  */
22
23#include "config.h"
24#include "system.h"
25#include "coretypes.h"
26#include "tm.h"
27#include "rtl.h"
28#include "vec.h"
29#include "predict.h"
30#include "bitmap.h"
31#include "basic-block.h"
32#include "df.h"
33#include "gcse-common.h"
34
35
36/* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
37   Note we store a pair of elements in the list, so they have to be
38   taken off pairwise.  */
39
40void
41canon_list_insert (rtx dest, const_rtx x ATTRIBUTE_UNUSED, void *data)
42{
43  rtx dest_addr, insn;
44  int bb;
45  modify_pair pair;
46
47  while (GET_CODE (dest) == SUBREG
48      || GET_CODE (dest) == ZERO_EXTRACT
49      || GET_CODE (dest) == STRICT_LOW_PART)
50    dest = XEXP (dest, 0);
51
52  /* If DEST is not a MEM, then it will not conflict with a load.  Note
53     that function calls are assumed to clobber memory, but are handled
54     elsewhere.  */
55
56  if (! MEM_P (dest))
57    return;
58
59  dest_addr = get_addr (XEXP (dest, 0));
60  dest_addr = canon_rtx (dest_addr);
61  insn = ((struct gcse_note_stores_info *)data)->insn;
62  bb = BLOCK_FOR_INSN (insn)->index;
63
64  pair.dest = dest;
65  pair.dest_addr = dest_addr;
66  vec<modify_pair> *canon_mem_list
67    = ((struct gcse_note_stores_info *)data)->canon_mem_list;
68  canon_mem_list[bb].safe_push (pair);
69}
70
71/* Record memory modification information for INSN.  We do not actually care
72   about the memory location(s) that are set, or even how they are set (consider
73   a CALL_INSN).  We merely need to record which insns modify memory.  */
74
75void
76record_last_mem_set_info_common (rtx_insn *insn,
77				 vec<rtx_insn *> *modify_mem_list,
78				 vec<modify_pair> *canon_modify_mem_list,
79				 bitmap modify_mem_list_set,
80				 bitmap blocks_with_calls)
81
82{
83  int bb;
84
85  bb = BLOCK_FOR_INSN (insn)->index;
86  modify_mem_list[bb].safe_push (insn);
87  bitmap_set_bit (modify_mem_list_set, bb);
88
89  if (CALL_P (insn))
90    bitmap_set_bit (blocks_with_calls, bb);
91  else
92    {
93      struct gcse_note_stores_info data;
94      data.insn = insn;
95      data.canon_mem_list = canon_modify_mem_list;
96      note_stores (PATTERN (insn), canon_list_insert, (void*) &data);
97    }
98}
99
100
101/* For each block, compute whether X is transparent.  X is either an
102   expression or an assignment [though we don't care which, for this context
103   an assignment is treated as an expression].  For each block where an
104   element of X is modified, reset the INDX bit in BMAP.
105
106   BLOCKS_WITH_CALLS indicates which blocks contain CALL_INSNs which kill
107   memory.
108
109   MODIFY_MEM_LIST_SET indicates which blocks have memory stores which might
110   kill a particular memory location.
111
112   CANON_MODIFY_MEM_LIST is the canonicalized list of memory locations modified
113   for each block.  */
114
115void
116compute_transp (const_rtx x, int indx, sbitmap *bmap,
117		bitmap blocks_with_calls,
118		bitmap modify_mem_list_set,
119	        vec<modify_pair> *canon_modify_mem_list)
120{
121  int i, j;
122  enum rtx_code code;
123  const char *fmt;
124
125  /* repeat is used to turn tail-recursion into iteration since GCC
126     can't do it when there's no return value.  */
127 repeat:
128
129  if (x == 0)
130    return;
131
132  code = GET_CODE (x);
133  switch (code)
134    {
135    case REG:
136	{
137	  df_ref def;
138	  for (def = DF_REG_DEF_CHAIN (REGNO (x));
139	       def;
140	       def = DF_REF_NEXT_REG (def))
141	    bitmap_clear_bit (bmap[DF_REF_BB (def)->index], indx);
142	}
143
144      return;
145
146    case MEM:
147      if (! MEM_READONLY_P (x))
148	{
149	  bitmap_iterator bi;
150	  unsigned bb_index;
151	  rtx x_addr;
152
153	  x_addr = get_addr (XEXP (x, 0));
154	  x_addr = canon_rtx (x_addr);
155
156	  /* First handle all the blocks with calls.  We don't need to
157	     do any list walking for them.  */
158	  EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi)
159	    {
160	      bitmap_clear_bit (bmap[bb_index], indx);
161	    }
162
163	  /* Now iterate over the blocks which have memory modifications
164	     but which do not have any calls.  */
165	  EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
166					  blocks_with_calls,
167					  0, bb_index, bi)
168	    {
169	      vec<modify_pair> list
170		= canon_modify_mem_list[bb_index];
171	      modify_pair *pair;
172	      unsigned ix;
173
174	      FOR_EACH_VEC_ELT_REVERSE (list, ix, pair)
175		{
176		  rtx dest = pair->dest;
177		  rtx dest_addr = pair->dest_addr;
178
179		  if (canon_true_dependence (dest, GET_MODE (dest),
180					     dest_addr, x, x_addr))
181		    {
182		      bitmap_clear_bit (bmap[bb_index], indx);
183		      break;
184		    }
185	        }
186	    }
187	}
188
189      x = XEXP (x, 0);
190      goto repeat;
191
192    case PC:
193    case CC0: /*FIXME*/
194    case CONST:
195    CASE_CONST_ANY:
196    case SYMBOL_REF:
197    case LABEL_REF:
198    case ADDR_VEC:
199    case ADDR_DIFF_VEC:
200      return;
201
202    default:
203      break;
204    }
205
206  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
207    {
208      if (fmt[i] == 'e')
209	{
210	  /* If we are about to do the last recursive call
211	     needed at this level, change it into iteration.
212	     This function is called enough to be worth it.  */
213	  if (i == 0)
214	    {
215	      x = XEXP (x, i);
216	      goto repeat;
217	    }
218
219	  compute_transp (XEXP (x, i), indx, bmap, blocks_with_calls,
220			  modify_mem_list_set, canon_modify_mem_list);
221	}
222      else if (fmt[i] == 'E')
223	for (j = 0; j < XVECLEN (x, i); j++)
224	  compute_transp (XVECEXP (x, i, j), indx, bmap, blocks_with_calls,
225			  modify_mem_list_set, canon_modify_mem_list);
226    }
227}
228