gcc/ree.c

   1 /* Redundant Extension Elimination pass for the GNU compiler.
   2    Copyright (C) 2010, 2011, 2012 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 "optabs.h"
 237 #include "insn-codes.h"
 238 #include "rtlhooks-def.h"
 239 #include "params.h"
 240 #include "tree-pass.h"
 241 #include "df.h"
 242 #include "cgraph.h"
 243
 244 /* This structure represents a candidate for elimination.  */
 245
 246 typedef struct GTY(()) ext_cand
 247 {
 248   /* The expression.  */
 249   const_rtx expr;
 250
 251   /* The kind of extension.  */
 252   enum rtx_code code;
 253
 254   /* The destination mode.  */
 255   enum machine_mode mode;
 256
 257   /* The instruction where it lives.  */
 258   rtx insn;
 259 } ext_cand;
 260
 261 DEF_VEC_O(ext_cand);
 262 DEF_VEC_ALLOC_O(ext_cand, heap);
 263
 264 static int max_insn_uid;
 265
 266 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
 267    and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
 268    this code modifies the SET rtx to a new SET rtx that extends the
 269    right hand expression into a register on the left hand side.  Note
 270    that multiple assumptions are made about the nature of the set that
 271    needs to be true for this to work and is called from merge_def_and_ext.
 272
 273    Original :
 274    (set (reg a) (expression))
 275
 276    Transform :
 277    (set (reg a) (any_extend (expression)))
 278
 279    Special Cases :
 280    If the expression is a constant or another extension, then directly
 281    assign it to the register.  */
 282
 283 static bool
 284 combine_set_extension (ext_cand *cand, rtx curr_insn, rtx *orig_set)
 285 {
 286   rtx orig_src = SET_SRC (*orig_set);
 287   rtx new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set)));
 288   rtx new_set;
 289
 290   /* Merge constants by directly moving the constant into the register under
 291      some conditions.  Recall that RTL constants are sign-extended.  */
 292   if (GET_CODE (orig_src) == CONST_INT
 293       && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode))
 294     {
 295       if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND)
 296         new_set = gen_rtx_SET (VOIDmode, new_reg, orig_src);
 297       else
 298         {
 299           /* Zero-extend the negative constant by masking out the bits outside
 300              the source mode.  */
 301           enum machine_mode src_mode = GET_MODE (SET_DEST (*orig_set));
 302           rtx new_const_int
 303             = GEN_INT (INTVAL (orig_src) & GET_MODE_MASK (src_mode));
 304           new_set = gen_rtx_SET (VOIDmode, new_reg, new_const_int);
 305         }
 306     }
 307   else if (GET_MODE (orig_src) == VOIDmode)
 308     {
 309       /* This is mostly due to a call insn that should not be optimized.  */
 310       return false;
 311     }
 312   else if (GET_CODE (orig_src) == cand->code)
 313     {
 314       /* Here is a sequence of two extensions.  Try to merge them.  */
 315       rtx temp_extension
 316         = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0));
 317       rtx simplified_temp_extension = simplify_rtx (temp_extension);
 318       if (simplified_temp_extension)
 319         temp_extension = simplified_temp_extension;
 320       new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
 321     }
 322   else if (GET_CODE (orig_src) == IF_THEN_ELSE)
 323     {
 324       /* Only IF_THEN_ELSE of phi-type copies are combined.  Otherwise,
 325          in general, IF_THEN_ELSE should not be combined.  */
 326       return false;
 327     }
 328   else
 329     {
 330       /* This is the normal case.  */
 331       rtx temp_extension
 332         = gen_rtx_fmt_e (cand->code, cand->mode, orig_src);
 333       rtx simplified_temp_extension = simplify_rtx (temp_extension);
 334       if (simplified_temp_extension)
 335         temp_extension = simplified_temp_extension;
 336       new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
 337     }
 338
 339   /* This change is a part of a group of changes.  Hence,
 340      validate_change will not try to commit the change.  */
 341   if (validate_change (curr_insn, orig_set, new_set, true))
 342     {
 343       if (dump_file)
 344         {
 345           fprintf (dump_file,
 346                    "Tentatively merged extension with definition:\n");
 347           print_rtl_single (dump_file, curr_insn);
 348         }
 349       return true;
 350     }
 351
 352   return false;
 353 }
 354
 355 /* Treat if_then_else insns, where the operands of both branches
 356    are registers, as copies.  For instance,
 357    Original :
 358    (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
 359    Transformed :
 360    (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
 361    DEF_INSN is the if_then_else insn.  */
 362
 363 static bool
 364 transform_ifelse (ext_cand *cand, rtx def_insn)
 365 {
 366   rtx set_insn = PATTERN (def_insn);
 367   rtx srcreg, dstreg, srcreg2;
 368   rtx map_srcreg, map_dstreg, map_srcreg2;
 369   rtx ifexpr;
 370   rtx cond;
 371   rtx new_set;
 372
 373   gcc_assert (GET_CODE (set_insn) == SET);
 374
 375   cond = XEXP (SET_SRC (set_insn), 0);
 376   dstreg = SET_DEST (set_insn);
 377   srcreg = XEXP (SET_SRC (set_insn), 1);
 378   srcreg2 = XEXP (SET_SRC (set_insn), 2);
 379   /* If the conditional move already has the right or wider mode,
 380      there is nothing to do.  */
 381   if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode))
 382     return true;
 383
 384   map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
 385   map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
 386   map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
 387   ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2);
 388   new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
 389
 390   if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
 391     {
 392       if (dump_file)
 393         {
 394           fprintf (dump_file,
 395                    "Mode of conditional move instruction extended:\n");
 396           print_rtl_single (dump_file, def_insn);
 397         }
 398       return true;
 399     }
 400
 401   return false;
 402 }
 403
 404 /* Get all the reaching definitions of an instruction.  The definitions are
 405    desired for REG used in INSN.  Return the definition list or NULL if a
 406    definition is missing.  If DEST is non-NULL, additionally push the INSN
 407    of the definitions onto DEST.  */
 408
 409 static struct df_link *
 410 get_defs (rtx insn, rtx reg, VEC (rtx,heap) **dest)
 411 {
 412   df_ref reg_info, *uses;
 413   struct df_link *ref_chain, *ref_link;
 414
 415   reg_info = NULL;
 416
 417   for (uses = DF_INSN_USES (insn); *uses; uses++)
 418     {
 419       reg_info = *uses;
 420       if (GET_CODE (DF_REF_REG (reg_info)) == SUBREG)
 421         return NULL;
 422       if (REGNO (DF_REF_REG (reg_info)) == REGNO (reg))
 423         break;
 424     }
 425
 426   gcc_assert (reg_info != NULL && uses != NULL);
 427
 428   ref_chain = DF_REF_CHAIN (reg_info);
 429
 430   for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
 431     {
 432       /* Problem getting some definition for this instruction.  */
 433       if (ref_link->ref == NULL)
 434         return NULL;
 435       if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
 436         return NULL;
 437     }
 438
 439   if (dest)
 440     for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
 441       VEC_safe_push (rtx, heap, *dest, DF_REF_INSN (ref_link->ref));
 442
 443   return ref_chain;
 444 }
 445
 446 /* Return true if INSN is
 447      (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
 448    and store x1 and x2 in REG_1 and REG_2.  */
 449
 450 static bool
 451 is_cond_copy_insn (rtx insn, rtx *reg1, rtx *reg2)
 452 {
 453   rtx expr = single_set (insn);
 454
 455   if (expr != NULL_RTX
 456       && GET_CODE (expr) == SET
 457       && GET_CODE (SET_DEST (expr)) == REG
 458       && GET_CODE (SET_SRC (expr))  == IF_THEN_ELSE
 459       && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
 460       && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
 461     {
 462       *reg1 = XEXP (SET_SRC (expr), 1);
 463       *reg2 = XEXP (SET_SRC (expr), 2);
 464       return true;
 465     }
 466
 467   return false;
 468 }
 469
 470 enum ext_modified_kind
 471 {
 472   /* The insn hasn't been modified by ree pass yet.  */
 473   EXT_MODIFIED_NONE,
 474   /* Changed into zero extension.  */
 475   EXT_MODIFIED_ZEXT,
 476   /* Changed into sign extension.  */
 477   EXT_MODIFIED_SEXT
 478 };
 479
 480 struct ext_modified
 481 {
 482   /* Mode from which ree has zero or sign extended the destination.  */
 483   ENUM_BITFIELD(machine_mode) mode : 8;
 484
 485   /* Kind of modification of the insn.  */
 486   ENUM_BITFIELD(ext_modified_kind) kind : 2;
 487
 488   /* True if the insn is scheduled to be deleted.  */
 489   unsigned int deleted : 1;
 490 };
 491
 492 /* Vectors used by combine_reaching_defs and its helpers.  */
 493 typedef struct ext_state
 494 {
 495   /* In order to avoid constant VEC_alloc/VEC_free, we keep these
 496      4 vectors live through the entire find_and_remove_re and just
 497      VEC_truncate them each time.  */
 498   VEC (rtx, heap) *defs_list;
 499   VEC (rtx, heap) *copies_list;
 500   VEC (rtx, heap) *modified_list;
 501   VEC (rtx, heap) *work_list;
 502
 503   /* For instructions that have been successfully modified, this is
 504      the original mode from which the insn is extending and
 505      kind of extension.  */
 506   struct ext_modified *modified;
 507 } ext_state;
 508
 509 /* Reaching Definitions of the extended register could be conditional copies
 510    or regular definitions.  This function separates the two types into two
 511    lists, STATE->DEFS_LIST and STATE->COPIES_LIST.  This is necessary because,
 512    if a reaching definition is a conditional copy, merging the extension with
 513    this definition is wrong.  Conditional copies are merged by transitively
 514    merging their definitions.  The defs_list is populated with all the reaching
 515    definitions of the extension instruction (EXTEND_INSN) which must be merged
 516    with an extension.  The copies_list contains all the conditional moves that
 517    will later be extended into a wider mode conditional move if all the merges
 518    are successful.  The function returns false upon failure, true upon
 519    success.  */
 520
 521 static bool
 522 make_defs_and_copies_lists (rtx extend_insn, const_rtx set_pat,
 523                             ext_state *state)
 524 {
 525   rtx src_reg = XEXP (SET_SRC (set_pat), 0);
 526   bool *is_insn_visited;
 527   bool ret = true;
 528
 529   VEC_truncate (rtx, state->work_list, 0);
 530
 531   /* Initialize the work list.  */
 532   if (!get_defs (extend_insn, src_reg, &state->work_list))
 533     gcc_unreachable ();
 534
 535   is_insn_visited = XCNEWVEC (bool, max_insn_uid);
 536
 537   /* Perform transitive closure for conditional copies.  */
 538   while (!VEC_empty (rtx, state->work_list))
 539     {
 540       rtx def_insn = VEC_pop (rtx, state->work_list);
 541       rtx reg1, reg2;
 542
 543       gcc_assert (INSN_UID (def_insn) < max_insn_uid);
 544
 545       if (is_insn_visited[INSN_UID (def_insn)])
 546         continue;
 547       is_insn_visited[INSN_UID (def_insn)] = true;
 548
 549       if (is_cond_copy_insn (def_insn, &reg1, &reg2))
 550         {
 551           /* Push it onto the copy list first.  */
 552           VEC_safe_push (rtx, heap, state->copies_list, def_insn);
 553
 554           /* Now perform the transitive closure.  */
 555           if (!get_defs (def_insn, reg1, &state->work_list)
 556               || !get_defs (def_insn, reg2, &state->work_list))
 557             {
 558               ret = false;
 559               break;
 560             }
 561         }
 562       else
 563         VEC_safe_push (rtx, heap, state->defs_list, def_insn);
 564     }
 565
 566   XDELETEVEC (is_insn_visited);
 567
 568   return ret;
 569 }
 570
 571 /* Merge the DEF_INSN with an extension.  Calls combine_set_extension
 572    on the SET pattern.  */
 573
 574 static bool
 575 merge_def_and_ext (ext_cand *cand, rtx def_insn, ext_state *state)
 576 {
 577   enum machine_mode ext_src_mode;
 578   enum rtx_code code;
 579   rtx *sub_rtx;
 580   rtx s_expr;
 581   int i;
 582
 583   ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
 584   code = GET_CODE (PATTERN (def_insn));
 585   sub_rtx = NULL;
 586
 587   if (code == PARALLEL)
 588     {
 589       for (i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
 590         {
 591           s_expr = XVECEXP (PATTERN (def_insn), 0, i);
 592           if (GET_CODE (s_expr) != SET)
 593             continue;
 594
 595           if (sub_rtx == NULL)
 596             sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
 597           else
 598             {
 599               /* PARALLEL with multiple SETs.  */
 600               return false;
 601             }
 602         }
 603     }
 604   else if (code == SET)
 605     sub_rtx = &PATTERN (def_insn);
 606   else
 607     {
 608       /* It is not a PARALLEL or a SET, what could it be ? */
 609       return false;
 610     }
 611
 612   gcc_assert (sub_rtx != NULL);
 613
 614   if (REG_P (SET_DEST (*sub_rtx))
 615       && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
 616           || ((state->modified[INSN_UID (def_insn)].kind
 617                == (cand->code == ZERO_EXTEND
 618                    ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
 619               && state->modified[INSN_UID (def_insn)].mode
 620                  == ext_src_mode)))
 621     {
 622       if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
 623           >= GET_MODE_SIZE (cand->mode))
 624         return true;
 625       /* If def_insn is already scheduled to be deleted, don't attempt
 626          to modify it.  */
 627       if (state->modified[INSN_UID (def_insn)].deleted)
 628         return false;
 629       if (combine_set_extension (cand, def_insn, sub_rtx))
 630         {
 631           if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
 632             state->modified[INSN_UID (def_insn)].mode = ext_src_mode;
 633           return true;
 634         }
 635     }
 636
 637   return false;
 638 }
 639
 640 /* This function goes through all reaching defs of the source
 641    of the candidate for elimination (CAND) and tries to combine
 642    the extension with the definition instruction.  The changes
 643    are made as a group so that even if one definition cannot be
 644    merged, all reaching definitions end up not being merged.
 645    When a conditional copy is encountered, merging is attempted
 646    transitively on its definitions.  It returns true upon success
 647    and false upon failure.  */
 648
 649 static bool
 650 combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
 651 {
 652   rtx def_insn;
 653   bool merge_successful = true;
 654   int i;
 655   int defs_ix;
 656   bool outcome;
 657
 658   VEC_truncate (rtx, state->defs_list, 0);
 659   VEC_truncate (rtx, state->copies_list, 0);
 660
 661   outcome = make_defs_and_copies_lists (cand->insn, set_pat, state);
 662
 663   if (!outcome)
 664     return false;
 665
 666   /* If cand->insn has been already modified, update cand->mode to a wider
 667      mode if possible, or punt.  */
 668   if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
 669     {
 670       enum machine_mode mode;
 671       rtx set;
 672
 673       if (state->modified[INSN_UID (cand->insn)].kind
 674           != (cand->code == ZERO_EXTEND
 675               ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)
 676           || state->modified[INSN_UID (cand->insn)].mode != cand->mode
 677           || (set = single_set (cand->insn)) == NULL_RTX)
 678         return false;
 679       mode = GET_MODE (SET_DEST (set));
 680       gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode));
 681       cand->mode = mode;
 682     }
 683
 684   merge_successful = true;
 685
 686   /* Go through the defs vector and try to merge all the definitions
 687      in this vector.  */
 688   VEC_truncate (rtx, state->modified_list, 0);
 689   FOR_EACH_VEC_ELT (rtx, state->defs_list, defs_ix, def_insn)
 690     {
 691       if (merge_def_and_ext (cand, def_insn, state))
 692         VEC_safe_push (rtx, heap, state->modified_list, def_insn);
 693       else
 694         {
 695           merge_successful = false;
 696           break;
 697         }
 698     }
 699
 700   /* Now go through the conditional copies vector and try to merge all
 701      the copies in this vector.  */
 702   if (merge_successful)
 703     {
 704       FOR_EACH_VEC_ELT (rtx, state->copies_list, i, def_insn)
 705         {
 706           if (transform_ifelse (cand, def_insn))
 707             VEC_safe_push (rtx, heap, state->modified_list, def_insn);
 708           else
 709             {
 710               merge_successful = false;
 711               break;
 712             }
 713         }
 714     }
 715
 716   if (merge_successful)
 717     {
 718       /* Commit the changes here if possible
 719          FIXME: It's an all-or-nothing scenario.  Even if only one definition
 720          cannot be merged, we entirely give up.  In the future, we should allow
 721          extensions to be partially eliminated along those paths where the
 722          definitions could be merged.  */
 723       if (apply_change_group ())
 724         {
 725           if (dump_file)
 726             fprintf (dump_file, "All merges were successful.\n");
 727
 728           FOR_EACH_VEC_ELT (rtx, state->modified_list, i, def_insn)
 729             if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
 730               state->modified[INSN_UID (def_insn)].kind
 731                 = (cand->code == ZERO_EXTEND
 732                    ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT);
 733
 734           return true;
 735         }
 736       else
 737         {
 738           /* Changes need not be cancelled explicitly as apply_change_group
 739              does it.  Print list of definitions in the dump_file for debug
 740              purposes.  This extension cannot be deleted.  */
 741           if (dump_file)
 742             {
 743               fprintf (dump_file,
 744                        "Merge cancelled, non-mergeable definitions:\n");
 745               FOR_EACH_VEC_ELT (rtx, state->modified_list, i, def_insn)
 746                 print_rtl_single (dump_file, def_insn);
 747             }
 748         }
 749     }
 750   else
 751     {
 752       /* Cancel any changes that have been made so far.  */
 753       cancel_changes (0);
 754     }
 755
 756   return false;
 757 }
 758
 759 /* Add an extension pattern that could be eliminated.  */
 760
 761 static void
 762 add_removable_extension (const_rtx expr, rtx insn,
 763                          VEC (ext_cand, heap) **insn_list,
 764                          unsigned *def_map)
 765 {
 766   enum rtx_code code;
 767   enum machine_mode mode;
 768   unsigned int idx;
 769   rtx src, dest;
 770
 771   /* We are looking for SET (REG N) (ANY_EXTEND (REG N)).  */
 772   if (GET_CODE (expr) != SET)
 773     return;
 774
 775   src = SET_SRC (expr);
 776   code = GET_CODE (src);
 777   dest = SET_DEST (expr);
 778   mode = GET_MODE (dest);
 779
 780   if (REG_P (dest)
 781       && (code == SIGN_EXTEND || code == ZERO_EXTEND)
 782       && REG_P (XEXP (src, 0))
 783       && REGNO (dest) == REGNO (XEXP (src, 0)))
 784     {
 785       struct df_link *defs, *def;
 786       ext_cand *cand;
 787
 788       /* First, make sure we can get all the reaching definitions.  */
 789       defs = get_defs (insn, XEXP (src, 0), NULL);
 790       if (!defs)
 791         {
 792           if (dump_file)
 793             {
 794               fprintf (dump_file, "Cannot eliminate extension:\n");
 795               print_rtl_single (dump_file, insn);
 796               fprintf (dump_file, " because of missing definition(s)\n");
 797             }
 798           return;
 799         }
 800
 801       /* Second, make sure the reaching definitions don't feed another and
 802          different extension.  FIXME: this obviously can be improved.  */
 803       for (def = defs; def; def = def->next)
 804         if ((idx = def_map[INSN_UID(DF_REF_INSN (def->ref))])
 805             && (cand = VEC_index (ext_cand, *insn_list, idx - 1))
 806             && (cand->code != code || cand->mode != mode))
 807           {
 808             if (dump_file)
 809               {
 810                 fprintf (dump_file, "Cannot eliminate extension:\n");
 811                 print_rtl_single (dump_file, insn);
 812                 fprintf (dump_file, " because of other extension\n");
 813               }
 814             return;
 815           }
 816
 817       /* Then add the candidate to the list and insert the reaching definitions
 818          into the definition map.  */
 819       cand = VEC_safe_push (ext_cand, heap, *insn_list, NULL);
 820       cand->expr = expr;
 821       cand->code = code;
 822       cand->mode = mode;
 823       cand->insn = insn;
 824       idx = VEC_length (ext_cand, *insn_list);
 825
 826       for (def = defs; def; def = def->next)
 827         def_map[INSN_UID(DF_REF_INSN (def->ref))] = idx;
 828     }
 829 }
 830
 831 /* Traverse the instruction stream looking for extensions and return the
 832    list of candidates.  */
 833
 834 static VEC (ext_cand, heap)*
 835 find_removable_extensions (void)
 836 {
 837   VEC (ext_cand, heap) *insn_list = NULL;
 838   basic_block bb;
 839   rtx insn, set;
 840   unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid);
 841
 842   FOR_EACH_BB (bb)
 843     FOR_BB_INSNS (bb, insn)
 844       {
 845         if (!NONDEBUG_INSN_P (insn))
 846           continue;
 847
 848         set = single_set (insn);
 849         if (set == NULL_RTX)
 850           continue;
 851         add_removable_extension (set, insn, &insn_list, def_map);
 852       }
 853
 854   XDELETEVEC (def_map);
 855
 856   return insn_list;
 857 }
 858
 859 /* This is the main function that checks the insn stream for redundant
 860    extensions and tries to remove them if possible.  */
 861
 862 static void
 863 find_and_remove_re (void)
 864 {
 865   ext_cand *curr_cand;
 866   rtx curr_insn = NULL_RTX;
 867   int num_re_opportunities = 0, num_realized = 0, i;
 868   VEC (ext_cand, heap) *reinsn_list;
 869   VEC (rtx, heap) *reinsn_del_list;
 870   ext_state state;
 871
 872   /* Construct DU chain to get all reaching definitions of each
 873      extension instruction.  */
 874   df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
 875   df_analyze ();
 876   df_set_flags (DF_DEFER_INSN_RESCAN);
 877
 878   max_insn_uid = get_max_uid ();
 879   reinsn_del_list = NULL;
 880   reinsn_list = find_removable_extensions ();
 881   state.defs_list = NULL;
 882   state.copies_list = NULL;
 883   state.modified_list = NULL;
 884   state.work_list = NULL;
 885   if (VEC_empty (ext_cand, reinsn_list))
 886     state.modified = NULL;
 887   else
 888     state.modified = XCNEWVEC (struct ext_modified, max_insn_uid);
 889
 890   FOR_EACH_VEC_ELT (ext_cand, reinsn_list, i, curr_cand)
 891     {
 892       num_re_opportunities++;
 893
 894       /* Try to combine the extension with the definition.  */
 895       if (dump_file)
 896         {
 897           fprintf (dump_file, "Trying to eliminate extension:\n");
 898           print_rtl_single (dump_file, curr_cand->insn);
 899         }
 900
 901       if (combine_reaching_defs (curr_cand, curr_cand->expr, &state))
 902         {
 903           if (dump_file)
 904             fprintf (dump_file, "Eliminated the extension.\n");
 905           num_realized++;
 906           VEC_safe_push (rtx, heap, reinsn_del_list, curr_cand->insn);
 907           state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
 908         }
 909     }
 910
 911   /* Delete all useless extensions here in one sweep.  */
 912   FOR_EACH_VEC_ELT (rtx, reinsn_del_list, i, curr_insn)
 913     delete_insn (curr_insn);
 914
 915   VEC_free (ext_cand, heap, reinsn_list);
 916   VEC_free (rtx, heap, reinsn_del_list);
 917   VEC_free (rtx, heap, state.defs_list);
 918   VEC_free (rtx, heap, state.copies_list);
 919   VEC_free (rtx, heap, state.modified_list);
 920   VEC_free (rtx, heap, state.work_list);
 921   XDELETEVEC (state.modified);
 922
 923   if (dump_file && num_re_opportunities > 0)
 924     fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
 925              num_re_opportunities, num_realized);
 926
 927   df_finish_pass (false);
 928 }
 929
 930 /* Find and remove redundant extensions.  */
 931
 932 static unsigned int
 933 rest_of_handle_ree (void)
 934 {
 935   timevar_push (TV_REE);
 936   find_and_remove_re ();
 937   timevar_pop (TV_REE);
 938   return 0;
 939 }
 940
 941 /* Run REE pass when flag_ree is set at optimization level > 0.  */
 942
 943 static bool
 944 gate_handle_ree (void)
 945 {
 946   return (optimize > 0 && flag_ree);
 947 }
 948
 949 struct rtl_opt_pass pass_ree =
 950 {
 951  {
 952   RTL_PASS,
 953   "ree",                                /* name */
 954   gate_handle_ree,                      /* gate */
 955   rest_of_handle_ree,                   /* execute */
 956   NULL,                                 /* sub */
 957   NULL,                                 /* next */
 958   0,                                    /* static_pass_number */
 959   TV_REE,                               /* tv_id */
 960   0,                                    /* properties_required */
 961   0,                                    /* properties_provided */
 962   0,                                    /* properties_destroyed */
 963   0,                                    /* todo_flags_start */
 964   TODO_ggc_collect |
 965   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 966  }
 967 };