gcc/ree.c

   1 /* Redundant Extension Elimination pass for the GNU compiler.
   2    Copyright (C) 2010, 2011 Free Software Foundation, Inc.
   3    Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
   4
   5    Based on the Redundant Zero-extension elimination pass contributed by
   6    Sriraman Tallam (tmsriram@google.com) and Silvius Rus (rus@google.com).
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 3, or (at your option) any later
  13 version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23
  24
  25 /* Problem Description :
  26    --------------------
  27    This pass is intended to remove redundant extension instructions.
  28    Such instructions appear for different reasons.  We expect some of
  29    them due to implicit zero-extension in 64-bit registers after writing
  30    to their lower 32-bit half (e.g. for the x86-64 architecture).
  31    Another possible reason is a type cast which follows a load (for
  32    instance a register restore) and which can be combined into a single
  33    instruction, and for which earlier local passes, e.g. the combiner,
  34    weren't able to optimize.
  35
  36    How does this pass work  ?
  37    --------------------------
  38
  39    This pass is run after register allocation.  Hence, all registers that
  40    this pass deals with are hard registers.  This pass first looks for an
  41    extension instruction that could possibly be redundant.  Such extension
  42    instructions show up in RTL with the pattern  :
  43    (set (reg:<SWI248> x) (any_extend:<SWI248> (reg:<SWI124> x))),
  44    where x can be any hard register.
  45    Now, this pass tries to eliminate this instruction by merging the
  46    extension with the definitions of register x.  For instance, if
  47    one of the definitions of register x was  :
  48    (set (reg:SI x) (plus:SI (reg:SI z1) (reg:SI z2))),
  49    followed by extension  :
  50    (set (reg:DI x) (zero_extend:DI (reg:SI x)))
  51    then the combination converts this into :
  52    (set (reg:DI x) (zero_extend:DI (plus:SI (reg:SI z1) (reg:SI z2)))).
  53    If all the merged definitions are recognizable assembly instructions,
  54    the extension is effectively eliminated.
  55
  56    For example, for the x86-64 architecture, implicit zero-extensions
  57    are captured with appropriate patterns in the i386.md file.  Hence,
  58    these merged definition can be matched to a single assembly instruction.
  59    The original extension instruction is then deleted if all the
  60    definitions can be merged.
  61
  62    However, there are cases where the definition instruction cannot be
  63    merged with an extension.  Examples are CALL instructions.  In such
  64    cases, the original extension is not redundant and this pass does
  65    not delete it.
  66
  67    Handling conditional moves :
  68    ----------------------------
  69
  70    Architectures like x86-64 support conditional moves whose semantics for
  71    extension differ from the other instructions.  For instance, the
  72    instruction *cmov ebx, eax*
  73    zero-extends eax onto rax only when the move from ebx to eax happens.
  74    Otherwise, eax may not be zero-extended.  Consider conditional moves as
  75    RTL instructions of the form
  76    (set (reg:SI x) (if_then_else (cond) (reg:SI y) (reg:SI z))).
  77    This pass tries to merge an extension with a conditional move by
  78    actually merging the definitions of y and z with an extension and then
  79    converting the conditional move into :
  80    (set (reg:DI x) (if_then_else (cond) (reg:DI y) (reg:DI z))).
  81    Since registers y and z are extended, register x will also be extended
  82    after the conditional move.  Note that this step has to be done
  83    transitively since the definition of a conditional copy can be
  84    another conditional copy.
  85
  86    Motivating Example I :
  87    ---------------------
  88    For this program :
  89    **********************************************
  90    bad_code.c
  91
  92    int mask[1000];
  93
  94    int foo(unsigned x)
  95    {
  96      if (x < 10)
  97        x = x * 45;
  98      else
  99        x = x * 78;
 100      return mask[x];
 101    }
 102    **********************************************
 103
 104    $ gcc -O2 bad_code.c
 105      ........
 106      400315:       b8 4e 00 00 00          mov    $0x4e,%eax
 107      40031a:       0f af f8                imul   %eax,%edi
 108      40031d:       89 ff                   mov    %edi,%edi - useless extension
 109      40031f:       8b 04 bd 60 19 40 00    mov    0x401960(,%rdi,4),%eax
 110      400326:       c3                      retq
 111      ......
 112      400330:       ba 2d 00 00 00          mov    $0x2d,%edx
 113      400335:       0f af fa                imul   %edx,%edi
 114      400338:       89 ff                   mov    %edi,%edi - useless extension
 115      40033a:       8b 04 bd 60 19 40 00    mov    0x401960(,%rdi,4),%eax
 116      400341:       c3                      retq
 117
 118    $ gcc -O2 -free bad_code.c
 119      ......
 120      400315:       6b ff 4e                imul   $0x4e,%edi,%edi
 121      400318:       8b 04 bd 40 19 40 00    mov    0x401940(,%rdi,4),%eax
 122      40031f:       c3                      retq
 123      400320:       6b ff 2d                imul   $0x2d,%edi,%edi
 124      400323:       8b 04 bd 40 19 40 00    mov    0x401940(,%rdi,4),%eax
 125      40032a:       c3                      retq
 126
 127    Motivating Example II :
 128    ---------------------
 129
 130    Here is an example with a conditional move.
 131
 132    For this program :
 133    **********************************************
 134
 135    unsigned long long foo(unsigned x , unsigned y)
 136    {
 137      unsigned z;
 138      if (x > 100)
 139        z = x + y;
 140      else
 141        z = x - y;
 142      return (unsigned long long)(z);
 143    }
 144
 145    $ gcc -O2 bad_code.c
 146      ............
 147      400360:       8d 14 3e                lea    (%rsi,%rdi,1),%edx
 148      400363:       89 f8                   mov    %edi,%eax
 149      400365:       29 f0                   sub    %esi,%eax
 150      400367:       83 ff 65                cmp    $0x65,%edi
 151      40036a:       0f 43 c2                cmovae %edx,%eax
 152      40036d:       89 c0                   mov    %eax,%eax - useless extension
 153      40036f:       c3                      retq
 154
 155    $ gcc -O2 -free bad_code.c
 156      .............
 157      400360:       89 fa                   mov    %edi,%edx
 158      400362:       8d 04 3e                lea    (%rsi,%rdi,1),%eax
 159      400365:       29 f2                   sub    %esi,%edx
 160      400367:       83 ff 65                cmp    $0x65,%edi
 161      40036a:       89 d6                   mov    %edx,%esi
 162      40036c:       48 0f 42 c6             cmovb  %rsi,%rax
 163      400370:       c3                      retq
 164
 165   Motivating Example III :
 166   ---------------------
 167
 168   Here is an example with a type cast.
 169
 170   For this program :
 171   **********************************************
 172
 173   void test(int size, unsigned char *in, unsigned char *out)
 174   {
 175     int i;
 176     unsigned char xr, xg, xy=0;
 177
 178     for (i = 0; i < size; i++) {
 179       xr = *in++;
 180       xg = *in++;
 181       xy = (unsigned char) ((19595*xr + 38470*xg) >> 16);
 182       *out++ = xy;
 183     }
 184   }
 185
 186   $ gcc -O2 bad_code.c
 187     ............
 188     10:   0f b6 0e                movzbl (%rsi),%ecx
 189     13:   0f b6 46 01             movzbl 0x1(%rsi),%eax
 190     17:   48 83 c6 02             add    $0x2,%rsi
 191     1b:   0f b6 c9                movzbl %cl,%ecx - useless extension
 192     1e:   0f b6 c0                movzbl %al,%eax - useless extension
 193     21:   69 c9 8b 4c 00 00       imul   $0x4c8b,%ecx,%ecx
 194     27:   69 c0 46 96 00 00       imul   $0x9646,%eax,%eax
 195
 196    $ gcc -O2 -free bad_code.c
 197      .............
 198     10:   0f b6 0e                movzbl (%rsi),%ecx
 199     13:   0f b6 46 01             movzbl 0x1(%rsi),%eax
 200     17:   48 83 c6 02             add    $0x2,%rsi
 201     1b:   69 c9 8b 4c 00 00       imul   $0x4c8b,%ecx,%ecx
 202     21:   69 c0 46 96 00 00       imul   $0x9646,%eax,%eax
 203
 204    Usefulness :
 205    ----------
 206
 207    The original redundant zero-extension elimination pass reported reduction
 208    of the dynamic instruction count of a compression benchmark by 2.8% and
 209    improvement of its run time by about 1%.
 210
 211    The additional performance gain with the enhanced pass is mostly expected
 212    on in-order architectures where redundancy cannot be compensated by out of
 213    order execution.  Measurements showed up to 10% performance gain (reduced
 214    run time) on EEMBC 2.0 benchmarks on Atom processor with geomean performance
 215    gain 1%.  */
 216
 217
 218 #include "config.h"
 219 #include "system.h"
 220 #include "coretypes.h"
 221 #include "tm.h"
 222 #include "rtl.h"
 223 #include "tree.h"
 224 #include "tm_p.h"
 225 #include "flags.h"
 226 #include "regs.h"
 227 #include "hard-reg-set.h"
 228 #include "basic-block.h"
 229 #include "insn-config.h"
 230 #include "function.h"
 231 #include "expr.h"
 232 #include "insn-attr.h"
 233 #include "recog.h"
 234 #include "diagnostic-core.h"
 235 #include "target.h"
 236 #include "timevar.h"
 237 #include "optabs.h"
 238 #include "insn-codes.h"
 239 #include "rtlhooks-def.h"
 240 /* Include output.h for dump_file.  */
 241 #include "output.h"
 242 #include "params.h"
 243 #include "timevar.h"
 244 #include "tree-pass.h"
 245 #include "df.h"
 246 #include "cgraph.h"
 247
 248 /* This structure represents a candidate for elimination.  */
 249
 250 typedef struct GTY(()) ext_cand
 251 {
 252   /* The expression.  */
 253   const_rtx expr;
 254
 255   /* The kind of extension.  */
 256   enum rtx_code code;
 257
 258   /* The destination mode.  */
 259   enum machine_mode mode;
 260
 261   /* The instruction where it lives.  */
 262   rtx insn;
 263 } ext_cand;
 264
 265 DEF_VEC_O(ext_cand);
 266 DEF_VEC_ALLOC_O(ext_cand, heap);
 267
 268 static int max_insn_uid;
 269
 270 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
 271    and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
 272    this code modifies the SET rtx to a new SET rtx that extends the
 273    right hand expression into a register on the left hand side.  Note
 274    that multiple assumptions are made about the nature of the set that
 275    needs to be true for this to work and is called from merge_def_and_ext.
 276
 277    Original :
 278    (set (reg a) (expression))
 279
 280    Transform :
 281    (set (reg a) (any_extend (expression)))
 282
 283    Special Cases :
 284    If the expression is a constant or another extension, then directly
 285    assign it to the register.  */
 286
 287 static bool
 288 combine_set_extension (ext_cand *cand, rtx curr_insn, rtx *orig_set)
 289 {
 290   rtx orig_src = SET_SRC (*orig_set);
 291   rtx new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set)));
 292   rtx new_set;
 293
 294   /* Merge constants by directly moving the constant into the register under
 295      some conditions.  Recall that RTL constants are sign-extended.  */
 296   if (GET_CODE (orig_src) == CONST_INT
 297       && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode))
 298     {
 299       if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND)
 300         new_set = gen_rtx_SET (VOIDmode, new_reg, orig_src);
 301       else
 302         {
 303           /* Zero-extend the negative constant by masking out the bits outside
 304              the source mode.  */
 305           enum machine_mode src_mode = GET_MODE (SET_DEST (*orig_set));
 306           rtx new_const_int
 307             = GEN_INT (INTVAL (orig_src) & GET_MODE_MASK (src_mode));
 308           new_set = gen_rtx_SET (VOIDmode, new_reg, new_const_int);
 309         }
 310     }
 311   else if (GET_MODE (orig_src) == VOIDmode)
 312     {
 313       /* This is mostly due to a call insn that should not be optimized.  */
 314       return false;
 315     }
 316   else if (GET_CODE (orig_src) == cand->code)
 317     {
 318       /* Here is a sequence of two extensions.  Try to merge them.  */
 319       rtx temp_extension
 320         = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0));
 321       rtx simplified_temp_extension = simplify_rtx (temp_extension);
 322       if (simplified_temp_extension)
 323         temp_extension = simplified_temp_extension;
 324       new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
 325     }
 326   else if (GET_CODE (orig_src) == IF_THEN_ELSE)
 327     {
 328       /* Only IF_THEN_ELSE of phi-type copies are combined.  Otherwise,
 329          in general, IF_THEN_ELSE should not be combined.  */
 330       return false;
 331     }
 332   else
 333     {
 334       /* This is the normal case.  */
 335       rtx temp_extension
 336         = gen_rtx_fmt_e (cand->code, cand->mode, orig_src);
 337       rtx simplified_temp_extension = simplify_rtx (temp_extension);
 338       if (simplified_temp_extension)
 339         temp_extension = simplified_temp_extension;
 340       new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
 341     }
 342
 343   /* This change is a part of a group of changes.  Hence,
 344      validate_change will not try to commit the change.  */
 345   if (validate_change (curr_insn, orig_set, new_set, true))
 346     {
 347       if (dump_file)
 348         {
 349           fprintf (dump_file, "Merged instruction with extension:\n");
 350           print_rtl_single (dump_file, curr_insn);
 351         }
 352       return true;
 353     }
 354
 355   return false;
 356 }
 357
 358 /* Treat if_then_else insns, where the operands of both branches
 359    are registers, as copies.  For instance,
 360    Original :
 361    (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
 362    Transformed :
 363    (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
 364    DEF_INSN is the if_then_else insn.  */
 365
 366 static bool
 367 transform_ifelse (ext_cand *cand, rtx def_insn)
 368 {
 369   rtx set_insn = PATTERN (def_insn);
 370   rtx srcreg, dstreg, srcreg2;
 371   rtx map_srcreg, map_dstreg, map_srcreg2;
 372   rtx ifexpr;
 373   rtx cond;
 374   rtx new_set;
 375
 376   gcc_assert (GET_CODE (set_insn) == SET);
 377
 378   cond = XEXP (SET_SRC (set_insn), 0);
 379   dstreg = SET_DEST (set_insn);
 380   srcreg = XEXP (SET_SRC (set_insn), 1);
 381   srcreg2 = XEXP (SET_SRC (set_insn), 2);
 382   map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
 383   map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
 384   map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
 385   ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2);
 386   new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
 387
 388   if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
 389     {
 390       if (dump_file)
 391         {
 392           fprintf (dump_file,
 393                    "Mode of conditional move instruction extended:\n");
 394           print_rtl_single (dump_file, def_insn);
 395         }
 396       return true;
 397     }
 398
 399   return false;
 400 }
 401
 402 /* Get all the reaching definitions of an instruction.  The definitions are
 403    desired for REG used in INSN.  Return the definition list or NULL if a
 404    definition is missing.  If DEST is non-NULL, additionally push the INSN
 405    of the definitions onto DEST.  */
 406
 407 static struct df_link *
 408 get_defs (rtx insn, rtx reg, VEC (rtx,heap) **dest)
 409 {
 410   df_ref reg_info, *defs;
 411   struct df_link *ref_chain, *ref_link;
 412
 413   reg_info = NULL;
 414
 415   for (defs = DF_INSN_USES (insn); *defs; defs++)
 416     {
 417       reg_info = *defs;
 418       if (GET_CODE (DF_REF_REG (reg_info)) == SUBREG)
 419         return NULL;
 420       if (REGNO (DF_REF_REG (reg_info)) == REGNO (reg))
 421         break;
 422     }
 423
 424   gcc_assert (reg_info != NULL && defs != NULL);
 425
 426   ref_chain = DF_REF_CHAIN (reg_info);
 427
 428   for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
 429     {
 430       /* Problem getting some definition for this instruction.  */
 431       if (ref_link->ref == NULL)
 432         return NULL;
 433       if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
 434         return NULL;
 435     }
 436
 437   if (dest)
 438     for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
 439       VEC_safe_push (rtx, heap, *dest, DF_REF_INSN (ref_link->ref));
 440
 441   return ref_chain;
 442 }
 443
 444 /* Return true if INSN is
 445      (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
 446    and store x1 and x2 in REG_1 and REG_2.  */
 447
 448 static bool
 449 is_cond_copy_insn (rtx insn, rtx *reg1, rtx *reg2)
 450 {
 451   rtx expr = single_set (insn);
 452
 453   if (expr != NULL_RTX
 454       && GET_CODE (expr) == SET
 455       && GET_CODE (SET_DEST (expr)) == REG
 456       && GET_CODE (SET_SRC (expr))  == IF_THEN_ELSE
 457       && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
 458       && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
 459     {
 460       *reg1 = XEXP (SET_SRC (expr), 1);
 461       *reg2 = XEXP (SET_SRC (expr), 2);
 462       return true;
 463     }
 464
 465   return false;
 466 }
 467
 468 /* Reaching Definitions of the extended register could be conditional copies
 469    or regular definitions.  This function separates the two types into two
 470    lists, DEFS_LIST and COPIES_LIST.  This is necessary because, if a reaching
 471    definition is a conditional copy, merging the extension with this definition
 472    is wrong.  Conditional copies are merged by transitively merging their
 473    definitions.  The defs_list is populated with all the reaching definitions
 474    of the extension instruction (EXTEND_INSN) which must be merged with an
 475    extension.  The copies_list contains all the conditional moves that will
 476    later be extended into a wider mode conditional move if all the merges are
 477    successful.  The function returns 0 upon failure, 1 upon success and 2 when
 478    all definitions of the EXTEND_INSN have been previously merged.  */
 479
 480 static int
 481 make_defs_and_copies_lists (rtx extend_insn, rtx set_pat,
 482                             VEC (rtx,heap) **defs_list,
 483                             VEC (rtx,heap) **copies_list)
 484 {
 485   VEC (rtx,heap) *work_list = VEC_alloc (rtx, heap, 8);
 486   rtx src_reg = XEXP (SET_SRC (set_pat), 0);
 487   bool *is_insn_visited;
 488   int ret = 1;
 489
 490   /* Initialize the work list.  */
 491   if (!get_defs (extend_insn, src_reg, &work_list))
 492     {
 493       VEC_free (rtx, heap, work_list);
 494       /* The number of defs being equal to zero can only mean that all the
 495          definitions have been previously merged.  */
 496       return 2;
 497     }
 498
 499   is_insn_visited = XCNEWVEC (bool, max_insn_uid);
 500
 501   /* Perform transitive closure for conditional copies.  */
 502   while (!VEC_empty (rtx, work_list))
 503     {
 504       rtx def_insn = VEC_pop (rtx, work_list);
 505       rtx reg1, reg2;
 506
 507       gcc_assert (INSN_UID (def_insn) < max_insn_uid);
 508
 509       if (is_insn_visited[INSN_UID (def_insn)])
 510         continue;
 511       is_insn_visited[INSN_UID (def_insn)] = true;
 512
 513       if (is_cond_copy_insn (def_insn, &reg1, &reg2))
 514         {
 515           /* Push it onto the copy list first.  */
 516           VEC_safe_push (rtx, heap, *copies_list, def_insn);
 517
 518           /* Now perform the transitive closure.  */
 519           if (!get_defs (def_insn, reg1, &work_list)
 520               || !get_defs (def_insn, reg2, &work_list))
 521             {
 522               ret = 0;
 523               break;
 524             }
 525         }
 526       else
 527         VEC_safe_push (rtx, heap, *defs_list, def_insn);
 528     }
 529
 530   XDELETEVEC (is_insn_visited);
 531   VEC_free (rtx, heap, work_list);
 532
 533   return ret;
 534 }
 535
 536 /* Merge the DEF_INSN with an extension.  Calls combine_set_extension
 537    on the SET pattern.  */
 538
 539 static bool
 540 merge_def_and_ext (ext_cand *cand, rtx def_insn)
 541 {
 542   enum machine_mode ext_src_mode;
 543   enum rtx_code code;
 544   rtx *sub_rtx;
 545   rtx s_expr;
 546   int i;
 547
 548   ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
 549   code = GET_CODE (PATTERN (def_insn));
 550   sub_rtx = NULL;
 551
 552   if (code == PARALLEL)
 553     {
 554       for (i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
 555         {
 556           s_expr = XVECEXP (PATTERN (def_insn), 0, i);
 557           if (GET_CODE (s_expr) != SET)
 558             continue;
 559
 560           if (sub_rtx == NULL)
 561             sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
 562           else
 563             {
 564               /* PARALLEL with multiple SETs.  */
 565               return false;
 566             }
 567         }
 568     }
 569   else if (code == SET)
 570     sub_rtx = &PATTERN (def_insn);
 571   else
 572     {
 573       /* It is not a PARALLEL or a SET, what could it be ? */
 574       return false;
 575     }
 576
 577   gcc_assert (sub_rtx != NULL);
 578
 579   if (GET_CODE (SET_DEST (*sub_rtx)) == REG
 580       && GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode)
 581     {
 582       return combine_set_extension (cand, def_insn, sub_rtx);
 583     }
 584
 585   return false;
 586 }
 587
 588 /* This function goes through all reaching defs of the source
 589    of the candidate for elimination (CAND) and tries to combine
 590    the extension with the definition instruction.  The changes
 591    are made as a group so that even if one definition cannot be
 592    merged, all reaching definitions end up not being merged.
 593    When a conditional copy is encountered, merging is attempted
 594    transitively on its definitions.  It returns true upon success
 595    and false upon failure.  */
 596
 597 static bool
 598 combine_reaching_defs (ext_cand *cand, rtx set_pat)
 599 {
 600   rtx def_insn;
 601   bool merge_successful = true;
 602   int i;
 603   int defs_ix;
 604   int outcome;
 605   VEC (rtx, heap) *defs_list, *copies_list, *vec;
 606
 607   defs_list = VEC_alloc (rtx, heap, 8);
 608   copies_list = VEC_alloc (rtx, heap, 8);
 609
 610   outcome = make_defs_and_copies_lists (cand->insn,
 611                                         set_pat, &defs_list, &copies_list);
 612
 613   /* outcome == 2 means that all the definitions for this extension have been
 614      previously merged when handling other extensions.  */
 615   if (outcome == 2)
 616     {
 617       VEC_free (rtx, heap, defs_list);
 618       VEC_free (rtx, heap, copies_list);
 619       if (dump_file)
 620         fprintf (dump_file, "All definitions have been previously merged.\n");
 621       return true;
 622     }
 623
 624   if (outcome == 0)
 625     {
 626       VEC_free (rtx, heap, defs_list);
 627       VEC_free (rtx, heap, copies_list);
 628       return false;
 629     }
 630
 631   merge_successful = true;
 632
 633   /* Go through the defs vector and try to merge all the definitions
 634      in this vector.  */
 635   vec = VEC_alloc (rtx, heap, 8);
 636   FOR_EACH_VEC_ELT (rtx, defs_list, defs_ix, def_insn)
 637     {
 638       if (merge_def_and_ext (cand, def_insn))
 639         VEC_safe_push (rtx, heap, vec, def_insn);
 640       else
 641         {
 642           merge_successful = false;
 643           break;
 644         }
 645     }
 646
 647   /* Now go through the conditional copies vector and try to merge all
 648      the copies in this vector.  */
 649   if (merge_successful)
 650     {
 651       FOR_EACH_VEC_ELT (rtx, copies_list, i, def_insn)
 652         {
 653           if (transform_ifelse (cand, def_insn))
 654             {
 655               VEC_safe_push (rtx, heap, vec, def_insn);
 656             }
 657           else
 658             {
 659               merge_successful = false;
 660               break;
 661             }
 662         }
 663     }
 664
 665   if (merge_successful)
 666     {
 667       /* Commit the changes here if possible
 668          FIXME: It's an all-or-nothing scenario.  Even if only one definition
 669          cannot be merged, we entirely give up.  In the future, we should allow
 670          extensions to be partially eliminated along those paths where the
 671          definitions could be merged.  */
 672       if (apply_change_group ())
 673         {
 674           if (dump_file)
 675             fprintf (dump_file, "All merges were successful.\n");
 676
 677           VEC_free (rtx, heap, vec);
 678           VEC_free (rtx, heap, defs_list);
 679           VEC_free (rtx, heap, copies_list);
 680           return true;
 681         }
 682       else
 683         {
 684           /* Changes need not be cancelled explicitly as apply_change_group
 685              does it.  Print list of definitions in the dump_file for debug
 686              purposes.  This extension cannot be deleted.  */
 687           if (dump_file)
 688             {
 689               FOR_EACH_VEC_ELT (rtx, vec, i, def_insn)
 690                 {
 691                   fprintf (dump_file, "Non-mergeable definitions:\n");
 692                   print_rtl_single (dump_file, def_insn);
 693                 }
 694             }
 695         }
 696     }
 697   else
 698     {
 699       /* Cancel any changes that have been made so far.  */
 700       cancel_changes (0);
 701     }
 702
 703   VEC_free (rtx, heap, vec);
 704   VEC_free (rtx, heap, defs_list);
 705   VEC_free (rtx, heap, copies_list);
 706
 707   return false;
 708 }
 709
 710 /* This structure holds information while walking the RTL stream.  */
 711
 712 struct re_info
 713 {
 714   /* The current insn.  */
 715   rtx insn;
 716
 717   /* The list of candidates.  */
 718   VEC (ext_cand, heap) *insn_list;
 719
 720   /* The map of definition instructions to candidates.  */
 721   ext_cand **def_map;
 722 };
 723
 724 /* Add an extension pattern that could be eliminated.  This is called via
 725    note_stores from find_removable_extensions.  */
 726
 727 static void
 728 add_removable_extension (rtx x ATTRIBUTE_UNUSED, const_rtx expr, void *data)
 729 {
 730   struct re_info *rei = (struct re_info *)data;
 731   enum rtx_code code;
 732   enum machine_mode mode;
 733   rtx src, dest;
 734
 735   /* We are looking for SET (REG N) (ANY_EXTEND (REG N)).  */
 736   if (GET_CODE (expr) != SET)
 737     return;
 738
 739   src = SET_SRC (expr);
 740   code = GET_CODE (src);
 741   dest = SET_DEST (expr);
 742   mode = GET_MODE (dest);
 743
 744   if (REG_P (dest)
 745       && (code == SIGN_EXTEND || code == ZERO_EXTEND)
 746       && REG_P (XEXP (src, 0))
 747       && REGNO (dest) == REGNO (XEXP (src, 0)))
 748     {
 749       struct df_link *defs, *def;
 750       ext_cand *cand;
 751
 752       /* First, make sure we can get all the reaching definitions.  */
 753       defs = get_defs (rei->insn, XEXP (src, 0), NULL);
 754       if (!defs)
 755         {
 756           if (dump_file)
 757             {
 758               fprintf (dump_file, "Cannot eliminate extension:\n");
 759               print_rtl_single (dump_file, rei->insn);
 760               fprintf (dump_file, " because of missing definition(s)\n");
 761             }
 762           return;
 763         }
 764
 765       /* Second, make sure the reaching definitions don't feed another and
 766          different extension.  FIXME: this obviously can be improved.  */
 767       for (def = defs; def; def = def->next)
 768         if ((cand = rei->def_map[INSN_UID(DF_REF_INSN (def->ref))])
 769             && (cand->code != code || cand->mode != mode))
 770           {
 771             if (dump_file)
 772               {
 773                 fprintf (dump_file, "Cannot eliminate extension:\n");
 774                 print_rtl_single (dump_file, rei->insn);
 775                 fprintf (dump_file, " because of other extension\n");
 776               }
 777             return;
 778           }
 779
 780       /* Then add the candidate to the list and insert the reaching definitions
 781          into the definition map.  */
 782       cand = VEC_safe_push (ext_cand, heap, rei->insn_list, NULL);
 783       cand->expr = expr;
 784       cand->code = code;
 785       cand->mode = mode;
 786       cand->insn = rei->insn;
 787
 788       for (def = defs; def; def = def->next)
 789         rei->def_map[INSN_UID(DF_REF_INSN (def->ref))] = cand;
 790     }
 791 }
 792
 793 /* Traverse the instruction stream looking for extensions and return the
 794    list of candidates.  */
 795
 796 static VEC (ext_cand, heap)*
 797 find_removable_extensions (void)
 798 {
 799   struct re_info rei;
 800   basic_block bb;
 801   rtx insn;
 802
 803   rei.insn_list = VEC_alloc (ext_cand, heap, 8);
 804   rei.def_map = XCNEWVEC (ext_cand *, max_insn_uid);
 805
 806   FOR_EACH_BB (bb)
 807     FOR_BB_INSNS (bb, insn)
 808       {
 809         if (!NONDEBUG_INSN_P (insn))
 810           continue;
 811
 812         rei.insn = insn;
 813         note_stores (PATTERN (insn), add_removable_extension, &rei);
 814       }
 815
 816   XDELETEVEC (rei.def_map);
 817
 818   return rei.insn_list;
 819 }
 820
 821 /* This is the main function that checks the insn stream for redundant
 822    extensions and tries to remove them if possible.  */
 823
 824 static void
 825 find_and_remove_re (void)
 826 {
 827   ext_cand *curr_cand;
 828   rtx curr_insn = NULL_RTX;
 829   int num_re_opportunities = 0, num_realized = 0, i;
 830   VEC (ext_cand, heap) *reinsn_list;
 831   VEC (rtx, heap) *reinsn_del_list;
 832
 833   /* Construct DU chain to get all reaching definitions of each
 834      extension instruction.  */
 835   df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
 836   df_analyze ();
 837
 838   max_insn_uid = get_max_uid ();
 839   reinsn_del_list = VEC_alloc (rtx, heap, 4);
 840   reinsn_list = find_removable_extensions ();
 841
 842   FOR_EACH_VEC_ELT (ext_cand, reinsn_list, i, curr_cand)
 843     {
 844       num_re_opportunities++;
 845
 846       /* Try to combine the extension with the definition.  */
 847       if (dump_file)
 848         {
 849           fprintf (dump_file, "Trying to eliminate extension:\n");
 850           print_rtl_single (dump_file, curr_cand->insn);
 851         }
 852
 853       if (combine_reaching_defs (curr_cand, PATTERN (curr_cand->insn)))
 854         {
 855           if (dump_file)
 856             fprintf (dump_file, "Eliminated the extension.\n");
 857           num_realized++;
 858           VEC_safe_push (rtx, heap, reinsn_del_list, curr_cand->insn);
 859         }
 860     }
 861
 862   /* Delete all useless extensions here in one sweep.  */
 863   FOR_EACH_VEC_ELT (rtx, reinsn_del_list, i, curr_insn)
 864     delete_insn (curr_insn);
 865
 866   VEC_free (ext_cand, heap, reinsn_list);
 867   VEC_free (rtx, heap, reinsn_del_list);
 868
 869   if (dump_file && num_re_opportunities > 0)
 870     fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
 871              num_re_opportunities, num_realized);
 872
 873   df_finish_pass (false);
 874 }
 875
 876 /* Find and remove redundant extensions.  */
 877
 878 static unsigned int
 879 rest_of_handle_ree (void)
 880 {
 881   timevar_push (TV_REE);
 882   find_and_remove_re ();
 883   timevar_pop (TV_REE);
 884   return 0;
 885 }
 886
 887 /* Run REE pass when flag_ree is set at optimization level > 0.  */
 888
 889 static bool
 890 gate_handle_ree (void)
 891 {
 892   return (optimize > 0 && flag_ree);
 893 }
 894
 895 struct rtl_opt_pass pass_ree =
 896 {
 897  {
 898   RTL_PASS,
 899   "ree",                                /* name */
 900   gate_handle_ree,                      /* gate */
 901   rest_of_handle_ree,                   /* execute */
 902   NULL,                                 /* sub */
 903   NULL,                                 /* next */
 904   0,                                    /* static_pass_number */
 905   TV_REE,                               /* tv_id */
 906   0,                                    /* properties_required */
 907   0,                                    /* properties_provided */
 908   0,                                    /* properties_destroyed */
 909   0,                                    /* todo_flags_start */
 910   TODO_ggc_collect |
 911   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 912  }
 913 };