gcc/struct-equiv.c

   1 /* Control flow optimization code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* This file contains helper functions for Cross jumping (tail merging).  */
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "tm.h"
  28 #include "rtl.h"
  29 #include "regs.h"
  30 #include "output.h"
  31 #include "insn-config.h"
  32 #include "flags.h"
  33 #include "recog.h"
  34 #include "tm_p.h"
  35 #include "target.h"
  36 #include "emit-rtl.h"
  37
  38 static void merge_memattrs (rtx, rtx);
  39
  40 \f
  41
  42 /* Removes the memory attributes of MEM expression
  43    if they are not equal.  */
  44
  45 void
  46 merge_memattrs (rtx x, rtx y)
  47 {
  48   int i;
  49   int j;
  50   enum rtx_code code;
  51   const char *fmt;
  52
  53   if (x == y)
  54     return;
  55   if (x == 0 || y == 0)
  56     return;
  57
  58   code = GET_CODE (x);
  59
  60   if (code != GET_CODE (y))
  61     return;
  62
  63   if (GET_MODE (x) != GET_MODE (y))
  64     return;
  65
  66   if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
  67     {
  68       if (! MEM_ATTRS (x))
  69         MEM_ATTRS (y) = 0;
  70       else if (! MEM_ATTRS (y))
  71         MEM_ATTRS (x) = 0;
  72       else
  73         {
  74           rtx mem_size;
  75
  76           if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
  77             {
  78               set_mem_alias_set (x, 0);
  79               set_mem_alias_set (y, 0);
  80             }
  81
  82           if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
  83             {
  84               set_mem_expr (x, 0);
  85               set_mem_expr (y, 0);
  86               set_mem_offset (x, 0);
  87               set_mem_offset (y, 0);
  88             }
  89           else if (MEM_OFFSET (x) != MEM_OFFSET (y))
  90             {
  91               set_mem_offset (x, 0);
  92               set_mem_offset (y, 0);
  93             }
  94
  95           if (!MEM_SIZE (x))
  96             mem_size = NULL_RTX;
  97           else if (!MEM_SIZE (y))
  98             mem_size = NULL_RTX;
  99           else
 100             mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
 101                                      INTVAL (MEM_SIZE (y))));
 102           set_mem_size (x, mem_size);
 103           set_mem_size (y, mem_size);
 104
 105           set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
 106           set_mem_align (y, MEM_ALIGN (x));
 107         }
 108     }
 109
 110   fmt = GET_RTX_FORMAT (code);
 111   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 112     {
 113       switch (fmt[i])
 114         {
 115         case 'E':
 116           /* Two vectors must have the same length.  */
 117           if (XVECLEN (x, i) != XVECLEN (y, i))
 118             return;
 119
 120           for (j = 0; j < XVECLEN (x, i); j++)
 121             merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
 122
 123           break;
 124
 125         case 'e':
 126           merge_memattrs (XEXP (x, i), XEXP (y, i));
 127         }
 128     }
 129   return;
 130 }
 131
 132 /* Check if the set of REG_DEAD notes attached to I1 and I2 allows us to
 133    go ahead with merging I1 and I2, which otherwise look fine.  */
 134 static bool
 135 death_notes_match_p (rtx i1 ATTRIBUTE_UNUSED, rtx i2 ATTRIBUTE_UNUSED,
 136                      int mode ATTRIBUTE_UNUSED)
 137 {
 138 #ifdef STACK_REGS
 139   /* If cross_jump_death_matters is not 0, the insn's mode
 140      indicates whether or not the insn contains any stack-like
 141      regs.  */
 142
 143   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
 144     {
 145       /* If register stack conversion has already been done, then
 146          death notes must also be compared before it is certain that
 147          the two instruction streams match.  */
 148
 149       rtx note;
 150       HARD_REG_SET i1_regset, i2_regset;
 151
 152       CLEAR_HARD_REG_SET (i1_regset);
 153       CLEAR_HARD_REG_SET (i2_regset);
 154
 155       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
 156         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 157           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
 158
 159       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
 160         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 161           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
 162
 163       GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
 164
 165       return false;
 166
 167     done:
 168       ;
 169     }
 170 #endif
 171   return true;
 172 }
 173
 174 /* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
 175
 176 bool
 177 insns_match_p (int mode, rtx i1, rtx i2)
 178 {
 179   rtx p1, p2;
 180
 181   /* Verify that I1 and I2 are equivalent.  */
 182   if (GET_CODE (i1) != GET_CODE (i2))
 183     return false;
 184
 185   p1 = PATTERN (i1);
 186   p2 = PATTERN (i2);
 187
 188   if (GET_CODE (p1) != GET_CODE (p2))
 189     return false;
 190
 191   /* If this is a CALL_INSN, compare register usage information.
 192      If we don't check this on stack register machines, the two
 193      CALL_INSNs might be merged leaving reg-stack.c with mismatching
 194      numbers of stack registers in the same basic block.
 195      If we don't check this on machines with delay slots, a delay slot may
 196      be filled that clobbers a parameter expected by the subroutine.
 197
 198      ??? We take the simple route for now and assume that if they're
 199      equal, they were constructed identically.  */
 200
 201   if (CALL_P (i1)
 202       && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
 203                         CALL_INSN_FUNCTION_USAGE (i2))
 204           || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
 205     return false;
 206
 207   if (!death_notes_match_p (i1, i2, mode))
 208     return false;
 209
 210   if (reload_completed
 211       ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
 212     return true;
 213
 214   /* Do not do EQUIV substitution after reload.  First, we're undoing the
 215      work of reload_cse.  Second, we may be undoing the work of the post-
 216      reload splitting pass.  */
 217   /* ??? Possibly add a new phase switch variable that can be used by
 218      targets to disallow the troublesome insns after splitting.  */
 219   if (!reload_completed)
 220     {
 221       /* The following code helps take care of G++ cleanups.  */
 222       rtx equiv1 = find_reg_equal_equiv_note (i1);
 223       rtx equiv2 = find_reg_equal_equiv_note (i2);
 224
 225       if (equiv1 && equiv2
 226           /* If the equivalences are not to a constant, they may
 227              reference pseudos that no longer exist, so we can't
 228              use them.  */
 229           && (! reload_completed
 230               || (CONSTANT_P (XEXP (equiv1, 0))
 231                   && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
 232         {
 233           rtx s1 = single_set (i1);
 234           rtx s2 = single_set (i2);
 235           if (s1 != 0 && s2 != 0
 236               && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
 237             {
 238               validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
 239               validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
 240               if (! rtx_renumbered_equal_p (p1, p2))
 241                 cancel_changes (0);
 242               else if (apply_change_group ())
 243                 return true;
 244             }
 245         }
 246     }
 247
 248   return false;
 249 }
 250 \f
 251 /* Look through the insns at the end of BB1 and BB2 and find the longest
 252    sequence that are equivalent.  Store the first insns for that sequence
 253    in *F1 and *F2 and return the sequence length.
 254
 255    To simplify callers of this function, if the blocks match exactly,
 256    store the head of the blocks in *F1 and *F2.  */
 257
 258 int
 259 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
 260                       basic_block bb2, rtx *f1, rtx *f2)
 261 {
 262   rtx i1, i2, last1, last2, afterlast1, afterlast2;
 263   int ninsns = 0;
 264
 265   /* Skip simple jumps at the end of the blocks.  Complex jumps still
 266      need to be compared for equivalence, which we'll do below.  */
 267
 268   i1 = BB_END (bb1);
 269   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
 270   if (onlyjump_p (i1)
 271       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
 272     {
 273       last1 = i1;
 274       i1 = PREV_INSN (i1);
 275     }
 276
 277   i2 = BB_END (bb2);
 278   if (onlyjump_p (i2)
 279       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
 280     {
 281       last2 = i2;
 282       /* Count everything except for unconditional jump as insn.  */
 283       if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
 284         ninsns++;
 285       i2 = PREV_INSN (i2);
 286     }
 287
 288   while (true)
 289     {
 290       /* Ignore notes.  */
 291       while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
 292         i1 = PREV_INSN (i1);
 293
 294       while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
 295         i2 = PREV_INSN (i2);
 296
 297       if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
 298         break;
 299
 300       if (!insns_match_p (mode, i1, i2))
 301         break;
 302
 303       merge_memattrs (i1, i2);
 304
 305       /* Don't begin a cross-jump with a NOTE insn.  */
 306       if (INSN_P (i1))
 307         {
 308           /* If the merged insns have different REG_EQUAL notes, then
 309              remove them.  */
 310           rtx equiv1 = find_reg_equal_equiv_note (i1);
 311           rtx equiv2 = find_reg_equal_equiv_note (i2);
 312
 313           if (equiv1 && !equiv2)
 314             remove_note (i1, equiv1);
 315           else if (!equiv1 && equiv2)
 316             remove_note (i2, equiv2);
 317           else if (equiv1 && equiv2
 318                    && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
 319             {
 320               remove_note (i1, equiv1);
 321               remove_note (i2, equiv2);
 322             }
 323
 324           afterlast1 = last1, afterlast2 = last2;
 325           last1 = i1, last2 = i2;
 326           ninsns++;
 327         }
 328
 329       i1 = PREV_INSN (i1);
 330       i2 = PREV_INSN (i2);
 331     }
 332
 333 #ifdef HAVE_cc0
 334   /* Don't allow the insn after a compare to be shared by
 335      cross-jumping unless the compare is also shared.  */
 336   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
 337     last1 = afterlast1, last2 = afterlast2, ninsns--;
 338 #endif
 339
 340   /* Include preceding notes and labels in the cross-jump.  One,
 341      this may bring us to the head of the blocks as requested above.
 342      Two, it keeps line number notes as matched as may be.  */
 343   if (ninsns)
 344     {
 345       while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
 346         last1 = PREV_INSN (last1);
 347
 348       if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
 349         last1 = PREV_INSN (last1);
 350
 351       while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
 352         last2 = PREV_INSN (last2);
 353
 354       if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
 355         last2 = PREV_INSN (last2);
 356
 357       *f1 = last1;
 358       *f2 = last2;
 359     }
 360
 361   return ninsns;
 362 }