gcc/gcse-common.c

   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
  40 void
  41 canon_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
  75 void
  76 record_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
 115 void
 116 compute_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 }