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