gcc/implicit-zee.c

   1 /* Redundant Zero-extension elimination for targets that implicitly
   2    zero-extend writes to the lower 32-bit portion of 64-bit registers.
   3    Copyright (C) 2010 Free Software Foundation, Inc.
   4    Contributed by Sriraman Tallam (tmsriram@google.com) and
   5                   Silvius Rus     (rus@google.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 3, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23
  24 /* Problem Description :
  25    --------------------
  26    This pass is intended to be applicable only to targets that implicitly
  27    zero-extend 64-bit registers after writing to their lower 32-bit half.
  28    For instance, x86_64 zero-extends the upper bits of a register
  29    implicitly whenever an instruction writes to its lower 32-bit half.
  30    For example, the instruction *add edi,eax* also zero-extends the upper
  31    32-bits of rax after doing the addition.  These zero extensions come
  32    for free and GCC does not always exploit this well.  That is, it has
  33    been observed that there are plenty of cases where GCC explicitly
  34    zero-extends registers for x86_64 that are actually useless because
  35    these registers were already implicitly zero-extended in a prior
  36    instruction.  This pass tries to eliminate such useless zero extension
  37    instructions.
  38
  39    How does this pass work  ?
  40    --------------------------
  41
  42    This pass is run after register allocation.  Hence, all registers that
  43    this pass deals with are hard registers.  This pass first looks for a
  44    zero-extension instruction that could possibly be redundant. Such zero
  45    extension instructions show up in RTL with the pattern :
  46    (set (reg:DI x) (zero_extend:DI (reg:SI x))).
  47    where x can be any one of the 64-bit hard registers.
  48    Now, this pass tries to eliminate this instruction by merging the
  49    zero-extension with the definitions of register x. For instance, if
  50    one of the definitions of register x was  :
  51    (set (reg:SI x) (plus:SI (reg:SI z1) (reg:SI z2))),
  52    then the combination converts this into :
  53    (set (reg:DI x) (zero_extend:DI (plus:SI (reg:SI z1) (reg:SI z2)))).
  54    If all the merged definitions are recognizable assembly instructions,
  55    the zero-extension is effectively eliminated.  For example, in x86_64,
  56    implicit zero-extensions are captured with appropriate patterns in the
  57    i386.md file.  Hence, these merged definition can be matched to a single
  58    assembly instruction.  The original zero-extension instruction is then
  59    deleted if all the definitions can be merged.
  60
  61    However, there are cases where the definition instruction cannot be
  62    merged with a zero-extend.  Examples are CALL instructions.  In such
  63    cases, the original zero extension is not redundant and this pass does
  64    not delete it.
  65
  66    Handling conditional moves :
  67    ----------------------------
  68
  69    Architectures like x86_64 support conditional moves whose semantics for
  70    zero-extension differ from the other instructions.  For instance, the
  71    instruction *cmov ebx, eax*
  72    zero-extends eax onto rax only when the move from ebx to eax happens.
  73    Otherwise, eax may not be zero-extended.  Conditional moves appear as
  74    RTL instructions of the form
  75    (set (reg:SI x) (if_then_else (cond) (reg:SI y) (reg:SI z))).
  76    This pass tries to merge a zero-extension with a conditional move by
  77    actually merging the defintions of y and z with a zero-extend and then
  78    converting the conditional move into :
  79    (set (reg:DI x) (if_then_else (cond) (reg:DI y) (reg:DI z))).
  80    Since registers y and z are zero-extended, register x will also be
  81    zero-extended after the conditional move.  Note that this step has to
  82    be done transitively since the definition of a conditional copy can be
  83    another conditional copy.
  84
  85    Motivating Example I :
  86    ---------------------
  87    For this program :
  88    **********************************************
  89    bad_code.c
  90
  91    int mask[1000];
  92
  93    int foo(unsigned x)
  94    {
  95      if (x < 10)
  96        x = x * 45;
  97      else
  98        x = x * 78;
  99      return mask[x];
 100    }
 101    **********************************************
 102
 103    $ gcc -O2 -fsee bad_code.c (Turned on existing sign-extension elimination.)
 104      ........
 105      400315:       b8 4e 00 00 00          mov    $0x4e,%eax
 106      40031a:       0f af f8                imul   %eax,%edi
 107      40031d:       89 ff                   mov    %edi,%edi  ---> Useless extend.
 108      40031f:       8b 04 bd 60 19 40 00    mov    0x401960(,%rdi,4),%eax
 109      400326:       c3                      retq
 110      ......
 111      400330:       ba 2d 00 00 00          mov    $0x2d,%edx
 112      400335:       0f af fa                imul   %edx,%edi
 113      400338:       89 ff                   mov    %edi,%edi  ---> Useless extend.
 114      40033a:       8b 04 bd 60 19 40 00    mov    0x401960(,%rdi,4),%eax
 115      400341:       c3                      retq
 116
 117    $ gcc -O2 -fzee bad_code.c
 118      ......
 119      400315:       6b ff 4e                imul   $0x4e,%edi,%edi
 120      400318:       8b 04 bd 40 19 40 00    mov    0x401940(,%rdi,4),%eax
 121      40031f:       c3                      retq
 122      400320:       6b ff 2d                imul   $0x2d,%edi,%edi
 123      400323:       8b 04 bd 40 19 40 00    mov    0x401940(,%rdi,4),%eax
 124      40032a:       c3                      retq
 125
 126    Motivating Example II :
 127    ---------------------
 128
 129    Here is an example with a conditional move.
 130
 131    For this program :
 132    **********************************************
 133
 134    unsigned long long foo(unsigned x , unsigned y)
 135    {
 136      unsigned z;
 137      if (x > 100)
 138        z = x + y;
 139      else
 140        z = x - y;
 141      return (unsigned long long)(z);
 142    }
 143
 144    $ gcc -O2 -fsee bad_code.c (Turned on existing sign-extension elimination.)
 145      ............
 146      400360:       8d 14 3e                lea    (%rsi,%rdi,1),%edx
 147      400363:       89 f8                   mov    %edi,%eax
 148      400365:       29 f0                   sub    %esi,%eax
 149      400367:       83 ff 65                cmp    $0x65,%edi
 150      40036a:       0f 43 c2                cmovae %edx,%eax
 151      40036d:       89 c0                   mov    %eax,%eax ---> Useless extend.
 152      40036f:       c3                      retq
 153
 154    $ gcc -O2 -fzee bad_code.c
 155      .............
 156      400360:       89 fa                   mov    %edi,%edx
 157      400362:       8d 04 3e                lea    (%rsi,%rdi,1),%eax
 158      400365:       29 f2                   sub    %esi,%edx
 159      400367:       83 ff 65                cmp    $0x65,%edi
 160      40036a:       89 d6                   mov    %edx,%esi
 161      40036c:       48 0f 42 c6             cmovb  %rsi,%rax
 162      400370:       c3                      retq
 163
 164
 165    Usefulness :
 166    ----------
 167
 168    This pass reduces the dynamic instruction count of a compression benchmark by
 169    2.8% and improves its run-time by about 1%.  The compression benchmark had the
 170    following code sequence in a very hot region of code before ZEE optimized it :
 171
 172    shr $0x5, %edx
 173    mov %edx, %edx --> Useless zero-extend.
 174
 175    How to turn on ?
 176    ----------------
 177    -fzee -O2.  */
 178
 179
 180 #include "config.h"
 181 #include "system.h"
 182 #include "coretypes.h"
 183 #include "tm.h"
 184 #include "rtl.h"
 185 #include "tree.h"
 186 #include "tm_p.h"
 187 #include "flags.h"
 188 #include "regs.h"
 189 #include "hard-reg-set.h"
 190 #include "basic-block.h"
 191 #include "insn-config.h"
 192 #include "function.h"
 193 #include "expr.h"
 194 #include "insn-attr.h"
 195 #include "recog.h"
 196 #include "toplev.h"
 197 #include "target.h"
 198 #include "timevar.h"
 199 #include "optabs.h"
 200 #include "insn-codes.h"
 201 #include "rtlhooks-def.h"
 202 /* Include output.h for dump_file.  */
 203 #include "output.h"
 204 #include "params.h"
 205 #include "timevar.h"
 206 #include "tree-pass.h"
 207 #include "df.h"
 208 #include "cgraph.h"
 209
 210 /* This says if a register is newly created for the purpose of
 211    zero-extension.  */
 212
 213 enum insn_merge_code
 214 {
 215   MERGE_NOT_ATTEMPTED = 0,
 216   MERGE_SUCCESS
 217 };
 218
 219 /* This says if a INSN UID or its definition has already been merged
 220    with a zero-extend or not.  */
 221
 222 static enum insn_merge_code *is_insn_merge_attempted;
 223 static int max_insn_uid;
 224
 225 /* Returns the merge code status for INSN.  */
 226
 227 static enum insn_merge_code
 228 get_insn_status (rtx insn)
 229 {
 230   gcc_assert (INSN_UID (insn) < max_insn_uid);
 231   return is_insn_merge_attempted[INSN_UID (insn)];
 232 }
 233
 234 /* Sets the merge code status of INSN to CODE.  */
 235
 236 static void
 237 set_insn_status (rtx insn, enum insn_merge_code code)
 238 {
 239   gcc_assert (INSN_UID (insn) < max_insn_uid);
 240   is_insn_merge_attempted[INSN_UID (insn)] = code;
 241 }
 242
 243 /* Check to see if this zero-extend matches a pattern
 244    that could be eliminated.  This is called via
 245    for_each_rtx in function find_and_remove_ze.  */
 246
 247 static int
 248 is_set_with_extension_DI (rtx *expr, void *data)
 249 {
 250   /* Looking only for patterns of the type :
 251      SET (REG:DI X) (ZERO_EXTEND (REG:SI x))
 252    */
 253
 254   if (GET_CODE (*expr) == SET
 255       && GET_MODE (SET_DEST (*expr)) == DImode
 256       && GET_CODE (SET_DEST (*expr)) == REG
 257       && GET_CODE (SET_SRC (*expr)) == ZERO_EXTEND
 258       && GET_CODE (XEXP (SET_SRC (*expr),0)) == REG
 259       && GET_MODE (XEXP (SET_SRC (*expr),0)) == SImode
 260       && REGNO (SET_DEST (*expr)) == REGNO (XEXP (SET_SRC (*expr),0)))
 261         {
 262           *(rtx **)(data) = expr;
 263           return 1;
 264         }
 265   return 0;
 266 }
 267
 268 /* Given a insn (CURR_INSN) and a pointer to the SET rtx (ORIG_SET)
 269    that needs to be modified, this code modifies the SET rtx to a
 270    new SET rtx that zero_extends the right hand expression into a DImode
 271    register (NEWREG) on the left hand side.  Note that multiple
 272    assumptions are made about the nature of the set that needs
 273    to be true for this to work and is called from merge_def_and_ze.
 274
 275    Original :
 276    (set (reg:SI a) (expression))
 277
 278    Transform :
 279    (set (reg:DI a) (zero_extend (expression)))
 280
 281    Special Cases :
 282    If the expression is a constant or another zero_extend directly
 283    assign it to the DI mode register.  */
 284
 285 static bool
 286 combine_set_zero_extend (rtx curr_insn, rtx *orig_set, rtx newreg)
 287 {
 288   rtx temp_extension, simplified_temp_extension, new_set, new_const_int;
 289   rtx orig_src;
 290   HOST_WIDE_INT val;
 291   unsigned int mask, delta_width;
 292
 293   /* Change the SET rtx and validate it.  */
 294   orig_src = SET_SRC (*orig_set);
 295   new_set = NULL_RTX;
 296
 297   /* The right hand side can also be VOIDmode.  These cases have to be
 298      handled differently.  */
 299
 300   if (GET_MODE (orig_src) != SImode)
 301     {
 302       /* Merge constants by directly moving the constant into the
 303          DImode register under some conditions.  */
 304
 305       if (GET_CODE (orig_src) == CONST_INT
 306           && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (SImode))
 307         {
 308           if (INTVAL (orig_src) >= 0)
 309             new_set = gen_rtx_SET (VOIDmode, newreg, orig_src);
 310           else if (INTVAL (orig_src) < 0)
 311             {
 312               /* Zero-extending a negative SImode integer into DImode
 313                  makes it a positive integer.  Convert the given negative
 314                  integer into the appropriate integer when zero-extended.  */
 315
 316               delta_width = HOST_BITS_PER_WIDE_INT - GET_MODE_BITSIZE (SImode);
 317               mask = (~(unsigned HOST_WIDE_INT) 0) >> delta_width;
 318               val = INTVAL (orig_src);
 319               val = val & mask;
 320               new_const_int = gen_rtx_CONST_INT (VOIDmode, val);
 321               new_set = gen_rtx_SET (VOIDmode, newreg, new_const_int);
 322             }
 323           else
 324             return false;
 325         }
 326       else
 327         {
 328           /* This is mostly due to a call insn that should not be
 329              optimized.  */
 330
 331           return false;
 332         }
 333     }
 334   else if (GET_CODE (orig_src) == ZERO_EXTEND)
 335     {
 336       /* Here a zero-extend is used to get to SI. Why not make it
 337          all the  way till DI.  */
 338
 339       temp_extension = gen_rtx_ZERO_EXTEND (DImode, XEXP (orig_src, 0));
 340       simplified_temp_extension = simplify_rtx (temp_extension);
 341       if (simplified_temp_extension)
 342         temp_extension = simplified_temp_extension;
 343       new_set = gen_rtx_SET (VOIDmode, newreg, temp_extension);
 344     }
 345   else if (GET_CODE (orig_src) == IF_THEN_ELSE)
 346     {
 347       /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
 348          in general, IF_THEN_ELSE should not be combined.  */
 349
 350       return false;
 351     }
 352   else
 353     {
 354       /* This is the normal case we expect.  */
 355
 356       temp_extension = gen_rtx_ZERO_EXTEND (DImode, orig_src);
 357       simplified_temp_extension = simplify_rtx (temp_extension);
 358       if (simplified_temp_extension)
 359         temp_extension = simplified_temp_extension;
 360       new_set = gen_rtx_SET (VOIDmode, newreg, temp_extension);
 361     }
 362
 363   gcc_assert (new_set != NULL_RTX);
 364
 365   /* This change is a part of a group of changes. Hence,
 366      validate_change will not try to commit the change.  */
 367
 368   if (validate_change (curr_insn, orig_set, new_set, true))
 369     {
 370       if (dump_file)
 371         {
 372           fprintf (dump_file, "Merged Instruction with ZERO_EXTEND:\n");
 373           print_rtl_single (dump_file, curr_insn);
 374         }
 375       return true;
 376     }
 377   return false;
 378 }
 379
 380 /* This returns the DI mode for the SI register REG_SI.  */
 381
 382 static rtx
 383 get_reg_di (rtx reg_si)
 384 {
 385   rtx newreg;
 386
 387   newreg = gen_rtx_REG (DImode, REGNO (reg_si));
 388   gcc_assert (newreg);
 389   return newreg;
 390 }
 391
 392 /* Treat if_then_else insns, where the operands of both branches
 393    are registers, as copies. For instance,
 394    Original :
 395    (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
 396    Transformed :
 397    (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
 398    DEF_INSN is the if_then_else insn.  */
 399
 400 static bool
 401 transform_ifelse (rtx def_insn)
 402 {
 403   rtx set_insn = PATTERN (def_insn);
 404   rtx srcreg, dstreg, srcreg2;
 405   rtx map_srcreg, map_dstreg, map_srcreg2;
 406   rtx ifexpr;
 407   rtx cond;
 408   rtx new_set;
 409
 410   gcc_assert (GET_CODE (set_insn) == SET);
 411   cond = XEXP (SET_SRC (set_insn), 0);
 412   dstreg = SET_DEST (set_insn);
 413   srcreg = XEXP (SET_SRC (set_insn), 1);
 414   srcreg2 = XEXP (SET_SRC (set_insn), 2);
 415   map_srcreg = get_reg_di (srcreg);
 416   map_srcreg2 = get_reg_di (srcreg2);
 417   map_dstreg = get_reg_di (dstreg);
 418   ifexpr = gen_rtx_IF_THEN_ELSE (DImode, cond, map_srcreg, map_srcreg2);
 419   new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
 420
 421   if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
 422     {
 423       if (dump_file)
 424         {
 425           fprintf (dump_file, "Cond_Move Instruction's mode extended :\n");
 426           print_rtl_single (dump_file, def_insn);
 427         }
 428       return true;
 429     }
 430   else
 431     return false;
 432 }
 433
 434 /* Function to get all the immediate definitions of an instruction.
 435    The reaching definitions are desired for WHICH_REG used in
 436    CURR_INSN.  This function returns 0 if there was an error getting
 437    a definition.  Upon success, this function returns the number of
 438    definitions and stores the definitions in DEST.  */
 439
 440 static int
 441 get_defs (rtx curr_insn, rtx which_reg, VEC (rtx,heap) **dest)
 442 {
 443   df_ref reg_info, *defs;
 444   struct df_link *def_chain;
 445   int n_refs = 0;
 446
 447   defs = DF_INSN_USES (curr_insn);
 448   reg_info = NULL;
 449
 450   while (*defs)
 451     {
 452       reg_info = *defs;
 453       if (GET_CODE (DF_REF_REG (reg_info)) == SUBREG)
 454         return 0;
 455       if (REGNO (DF_REF_REG (reg_info)) == REGNO (which_reg))
 456         break;
 457       defs++;
 458     }
 459
 460   gcc_assert (reg_info != NULL && defs != NULL);
 461   def_chain = DF_REF_CHAIN (reg_info);
 462
 463   while (def_chain)
 464     {
 465       /* Problem getting some definition for this instruction.  */
 466
 467       if (def_chain->ref == NULL)
 468         return 0;
 469       if (DF_REF_INSN_INFO (def_chain->ref) == NULL)
 470         return 0;
 471       def_chain = def_chain->next;
 472     }
 473
 474   def_chain = DF_REF_CHAIN (reg_info);
 475
 476   if (dest == NULL)
 477     return 1;
 478
 479   while (def_chain)
 480     {
 481       VEC_safe_push (rtx, heap, *dest, DF_REF_INSN (def_chain->ref));
 482       def_chain = def_chain->next;
 483       n_refs++;
 484     }
 485   return n_refs;
 486 }
 487
 488 /* rtx function to check if this SET insn, EXPR, is a conditional copy insn :
 489    (set (reg:SI a ) (IF_THEN_ELSE (cond) (reg:SI b) (reg:SI c)))
 490    Called from is_insn_cond_copy.  DATA stores the two registers on each
 491    side of the condition.  */
 492
 493 static int
 494 is_this_a_cmove (rtx expr, void *data)
 495 {
 496   /* Check for conditional (if-then-else) copy.  */
 497
 498   if (GET_CODE (expr) == SET
 499       && GET_CODE (SET_DEST (expr)) == REG
 500       && GET_MODE (SET_DEST (expr)) == SImode
 501       && GET_CODE (SET_SRC (expr))  == IF_THEN_ELSE
 502       && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
 503       && GET_MODE (XEXP (SET_SRC (expr), 1)) == SImode
 504       && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG
 505       && GET_MODE (XEXP (SET_SRC (expr), 2)) == SImode)
 506     {
 507       ((rtx *)data)[0] = XEXP (SET_SRC (expr), 1);
 508       ((rtx *)data)[1] = XEXP (SET_SRC (expr), 2);
 509       return 1;
 510     }
 511   return 0;
 512 }
 513
 514 /* This returns 1 if it found
 515    (SET (reg:SI REGNO (def_reg)) (if_then_else (cond) (REG:SI x1) (REG:SI x2)))
 516    in the DEF_INSN pattern.  It stores the x1 and x2 in COPY_REG_1
 517    and COPY_REG_2.  */
 518
 519 static int
 520 is_insn_cond_copy (rtx def_insn, rtx *copy_reg_1, rtx *copy_reg_2)
 521 {
 522   int type;
 523   rtx set_expr;
 524   rtx srcreg[2];
 525
 526   srcreg[0] = NULL_RTX;
 527   srcreg[1] = NULL_RTX;
 528
 529   set_expr = single_set (def_insn);
 530
 531   if (set_expr == NULL_RTX)
 532     return 0;
 533
 534   type = is_this_a_cmove (set_expr, (void *) srcreg);
 535
 536   if (type)
 537     {
 538       *copy_reg_1 = srcreg[0];
 539       *copy_reg_2 = srcreg[1];
 540       return type;
 541     }
 542
 543   return 0;
 544 }
 545
 546 /* Reaching Definitions of the zero-extended register could be conditional
 547    copies or regular definitions.  This function separates the two types into
 548    two lists, DEFS_LIST and COPIES_LIST.  This is necessary because, if a
 549    reaching definition is a conditional copy, combining the zero_extend with
 550    this definition is wrong.  Conditional copies are merged by transitively
 551    merging its definitions.  The defs_list is populated with all the reaching
 552    definitions of the zero-extension instruction (ZERO_EXTEND_INSN) which must
 553    be merged with a zero_extend.  The copies_list contains all the conditional
 554    moves that will later be extended into a DI mode conditonal move if all the
 555    merges are successful.  The function returns false when there is a failure
 556    in getting some definitions, like that of parameters.  It returns 1 upon
 557    success, 0 upon failure and 2 when all definitions of the ZERO_EXTEND_INSN
 558    were merged previously.  */
 559
 560 static int
 561 make_defs_and_copies_lists (rtx zero_extend_insn, rtx set_pat,
 562                             VEC (rtx,heap) **defs_list,
 563                             VEC (rtx,heap) **copies_list)
 564 {
 565   bool *is_insn_visited;
 566   VEC (rtx,heap) *work_list;
 567   rtx srcreg, copy_reg_1, copy_reg_2;
 568   rtx def_insn;
 569   int n_defs = 0;
 570   int vec_index = 0;
 571   int n_worklist = 0;
 572   int i, is_copy;
 573
 574   srcreg = XEXP (SET_SRC (set_pat), 0);
 575   work_list = VEC_alloc (rtx, heap, 8);
 576
 577   /* Initialize the Work List */
 578   n_worklist = get_defs (zero_extend_insn, srcreg, &work_list);
 579
 580   if (n_worklist == 0)
 581     {
 582       VEC_free (rtx, heap, work_list);
 583       /* The number of defs being equal to zero can only imply that all of its
 584          definitions have been previously merged.  */
 585       return 2;
 586     }
 587
 588   is_insn_visited = XNEWVEC (bool, max_insn_uid);
 589
 590   for (i = 0; i < max_insn_uid; i++)
 591     is_insn_visited[i] = false;
 592
 593
 594   /* Perform transitive closure for conditional copies.  */
 595   while (n_worklist > vec_index)
 596     {
 597       def_insn = VEC_index (rtx, work_list, vec_index);
 598       gcc_assert (INSN_UID (def_insn) < max_insn_uid);
 599
 600       if (is_insn_visited[INSN_UID (def_insn)])
 601         {
 602           vec_index++;
 603           continue;
 604         }
 605
 606       is_insn_visited[INSN_UID (def_insn)] = true;
 607       copy_reg_1 = copy_reg_2 = NULL_RTX;
 608       is_copy = is_insn_cond_copy (def_insn, &copy_reg_1, &copy_reg_2);
 609       if (is_copy)
 610         {
 611           gcc_assert (copy_reg_1 && copy_reg_2);
 612
 613           /* Push it into the copy list first.  */
 614
 615           VEC_safe_push (rtx, heap, *copies_list, def_insn);
 616
 617           /* Perform transitive closure here */
 618
 619           n_defs = get_defs (def_insn, copy_reg_1, &work_list);
 620
 621           if (n_defs == 0)
 622             {
 623               VEC_free (rtx, heap, work_list);
 624               XDELETEVEC (is_insn_visited);
 625               return 0;
 626             }
 627           n_worklist += n_defs;
 628
 629           n_defs = get_defs (def_insn, copy_reg_2, &work_list);
 630           if (n_defs == 0)
 631             {
 632               VEC_free (rtx, heap, work_list);
 633               XDELETEVEC (is_insn_visited);
 634               return 0;
 635             }
 636           n_worklist += n_defs;
 637         }
 638       else
 639         {
 640           VEC_safe_push (rtx, heap, *defs_list, def_insn);
 641         }
 642       vec_index++;
 643     }
 644
 645   VEC_free (rtx, heap, work_list);
 646   XDELETEVEC (is_insn_visited);
 647   return 1;
 648 }
 649
 650 /* Merge the DEF_INSN with a zero-extend.  Calls combine_set_zero_extend
 651    on the SET pattern.  */
 652
 653 static bool
 654 merge_def_and_ze (rtx def_insn)
 655 {
 656   enum rtx_code code;
 657   rtx setreg;
 658   rtx *sub_rtx;
 659   rtx s_expr;
 660   int i;
 661
 662   code = GET_CODE (PATTERN (def_insn));
 663   sub_rtx = NULL;
 664
 665   if (code == PARALLEL)
 666     {
 667       for (i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
 668         {
 669           s_expr = XVECEXP (PATTERN (def_insn), 0, i);
 670           if (GET_CODE (s_expr) != SET)
 671             continue;
 672
 673           if (sub_rtx == NULL)
 674             sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
 675           else
 676             {
 677               /* PARALLEL with multiple SETs.  */
 678               return false;
 679             }
 680         }
 681     }
 682   else if (code == SET)
 683     sub_rtx = &PATTERN (def_insn);
 684   else
 685     {
 686       /* It is not a PARALLEL or a SET, what could it be ? */
 687       return false;
 688     }
 689
 690   gcc_assert (sub_rtx != NULL);
 691
 692   if (GET_CODE (SET_DEST (*sub_rtx)) == REG
 693       && GET_MODE (SET_DEST (*sub_rtx)) == SImode)
 694     {
 695       setreg = get_reg_di (SET_DEST (*sub_rtx));
 696       return combine_set_zero_extend (def_insn, sub_rtx, setreg);
 697     }
 698   else
 699     return false;
 700   return true;
 701 }
 702
 703 /* This function goes through all reaching defs of the source
 704    of the zero extension instruction (ZERO_EXTEND_INSN) and
 705    tries to combine the zero extension with the definition
 706    instruction.  The changes are made as a group so that even
 707    if one definition cannot be merged, all reaching definitions
 708    end up not being merged. When a conditional copy is encountered,
 709    merging is attempted transitively on its definitions.  It returns
 710    true upon success and false upon failure.  */
 711
 712 static bool
 713 combine_reaching_defs (rtx zero_extend_insn, rtx set_pat)
 714 {
 715   rtx def_insn;
 716   bool merge_successful = true;
 717   int i;
 718   int defs_ix;
 719   int outcome;
 720
 721   /* To store the definitions that have been merged.  */
 722
 723   VEC (rtx, heap) *defs_list, *copies_list, *vec;
 724   enum insn_merge_code merge_code;
 725
 726   defs_list = VEC_alloc (rtx, heap, 8);
 727   copies_list = VEC_alloc (rtx, heap, 8);
 728
 729   outcome = make_defs_and_copies_lists (zero_extend_insn,
 730                                         set_pat, &defs_list, &copies_list);
 731
 732   /* outcome == 2 implies that all the definitions for this zero_extend were
 733      merged while previously when handling other zero_extends.  */
 734
 735   if (outcome == 2)
 736     {
 737       VEC_free (rtx, heap, defs_list);
 738       VEC_free (rtx, heap, copies_list);
 739       if (dump_file)
 740         fprintf (dump_file, "All definitions have been merged previously...\n");
 741       return true;
 742     }
 743
 744   if (outcome == 0)
 745     {
 746       VEC_free (rtx, heap, defs_list);
 747       VEC_free (rtx, heap, copies_list);
 748       return false;
 749     }
 750
 751   merge_successful = true;
 752
 753   /* Go through the defs vector and try to merge all the definitions
 754      in this vector.  */
 755
 756   vec = VEC_alloc (rtx, heap, 8);
 757   for (defs_ix = 0; VEC_iterate (rtx, defs_list, defs_ix, def_insn); defs_ix++)
 758     {
 759       merge_code = get_insn_status (def_insn);
 760       gcc_assert (merge_code == MERGE_NOT_ATTEMPTED);
 761
 762       if (merge_def_and_ze (def_insn))
 763         VEC_safe_push (rtx, heap, vec, def_insn);
 764       else
 765         {
 766           merge_successful = false;
 767           break;
 768         }
 769     }
 770
 771   /* Now go through the conditional copies vector and try to merge all
 772      the copies in this vector.  */
 773
 774   if (merge_successful)
 775     {
 776       for (i = 0; VEC_iterate (rtx, copies_list, i, def_insn); i++)
 777         {
 778           if (transform_ifelse (def_insn))
 779             {
 780               VEC_safe_push (rtx, heap, vec, def_insn);
 781             }
 782           else
 783             {
 784               merge_successful = false;
 785               break;
 786             }
 787         }
 788     }
 789
 790   if (merge_successful)
 791     {
 792       /* Commit the changes here if possible */
 793       /* XXX : Now, it is an all or nothing scenario.  Even if one definition
 794          cannot be merged we totally bail.  In future, allow zero-extensions to
 795          be partially eliminated along those paths where the definitions could
 796          be merged.  */
 797
 798       if (apply_change_group ())
 799         {
 800           if (dump_file)
 801             fprintf (dump_file, "All merges were successful ....\n");
 802
 803           for (i = 0; VEC_iterate (rtx, vec, i, def_insn); i++)
 804             {
 805               set_insn_status (def_insn, MERGE_SUCCESS);
 806             }
 807
 808           VEC_free (rtx, heap, vec);
 809           VEC_free (rtx, heap, defs_list);
 810           VEC_free (rtx, heap, copies_list);
 811           return true;
 812         }
 813       else
 814         {
 815           /* Changes need not be cancelled explicitly as apply_change_group ()
 816              does it.   Print list of definitions in the dump_file for debug
 817              purposes.  This zero-extension cannot be deleted.  */
 818
 819           if (dump_file)
 820             {
 821               for (i = 0; VEC_iterate (rtx, vec, i, def_insn); i++)
 822                 {
 823                   fprintf (dump_file, " Ummergable definitions : \n");
 824                   print_rtl_single (dump_file, def_insn);
 825                 }
 826             }
 827         }
 828     }
 829   else
 830     {
 831       /* Cancel any changes that have been made so far.  */
 832       cancel_changes (0);
 833     }
 834
 835   VEC_free (rtx, heap, vec);
 836   VEC_free (rtx, heap, defs_list);
 837   VEC_free (rtx, heap, copies_list);
 838   return false;
 839 }
 840
 841 /* Goes through the instruction stream looking for zero-extends.  If the zero
 842    extension instruction has atleast one def it adds it to a list of possible
 843    candidates for deletion.  It returns the list of candidates.  */
 844
 845 static VEC (rtx,heap)*
 846 find_removable_zero_extends (void)
 847 {
 848   VEC (rtx, heap) *zeinsn_list;
 849   basic_block curr_block;
 850   rtx curr_insn;
 851   rtx *set_insn;
 852   rtx which_reg;
 853   int type ;
 854   int has_defs;
 855
 856   zeinsn_list = VEC_alloc (rtx, heap, 8);
 857   FOR_EACH_BB (curr_block)
 858     {
 859       FOR_BB_INSNS (curr_block, curr_insn)
 860         {
 861           if (!INSN_P (curr_insn))
 862             continue;
 863
 864           type = for_each_rtx (&PATTERN (curr_insn),
 865                                is_set_with_extension_DI,
 866                                (void *)&set_insn);
 867
 868           if (!type)
 869             continue;
 870
 871           which_reg = XEXP (SET_SRC (*set_insn), 0);
 872           has_defs = get_defs (curr_insn, which_reg, NULL);
 873           if (has_defs)
 874             VEC_safe_push (rtx, heap, zeinsn_list, curr_insn);
 875           else if (dump_file)
 876             {
 877               fprintf (dump_file, "Cannot eliminate zero extension : \n");
 878               print_rtl_single (dump_file, curr_insn);
 879               fprintf (dump_file,
 880                        "This has no defs. Could be extending parameters.\n");
 881             }
 882         }
 883     }
 884   return zeinsn_list;
 885 }
 886
 887 /* This is the main function that checks the insn stream for redundant
 888    zero extensions and tries to remove them if possible.  */
 889
 890 static unsigned int
 891 find_and_remove_ze (void)
 892 {
 893   rtx curr_insn = NULL_RTX;
 894   int i;
 895   int ix;
 896   long long num_realized = 0;
 897   long long num_ze_opportunities = 0;
 898   VEC (rtx, heap) *zeinsn_list;
 899   VEC (rtx, heap) *zeinsn_del_list;
 900
 901   /* Construct DU chain to get all reaching definitions of each
 902      zero-extension instruction.  */
 903
 904   df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
 905   df_analyze ();
 906
 907   max_insn_uid = get_max_uid ();
 908
 909   is_insn_merge_attempted = XNEWVEC (enum insn_merge_code,
 910                                      sizeof (enum insn_merge_code)* max_insn_uid);
 911
 912   for (i = 0; i < max_insn_uid; i++)
 913     {
 914       is_insn_merge_attempted[i] = MERGE_NOT_ATTEMPTED;
 915     }
 916
 917   num_ze_opportunities = num_realized = 0;
 918
 919   zeinsn_del_list = VEC_alloc (rtx, heap, 4);
 920
 921   zeinsn_list = find_removable_zero_extends ();
 922
 923   for (ix = 0; VEC_iterate (rtx, zeinsn_list, ix, curr_insn); ix++)
 924     {
 925       num_ze_opportunities++;
 926       /* Try to combine the zero-extends with the definition here.  */
 927
 928       if (dump_file)
 929         {
 930           fprintf (dump_file, "Trying to eliminate zero extension : \n");
 931           print_rtl_single (dump_file, curr_insn);
 932         }
 933
 934       if (combine_reaching_defs (curr_insn, PATTERN (curr_insn)))
 935         {
 936           if (dump_file)
 937             fprintf (dump_file, "Eliminated the zero extension...\n");
 938           num_realized++;
 939           VEC_safe_push (rtx, heap, zeinsn_del_list, curr_insn);
 940         }
 941     }
 942
 943   /* Delete all useless zero extensions here in one sweep.  */
 944   for (ix = 0; VEC_iterate (rtx, zeinsn_del_list, ix, curr_insn); ix++)
 945     {
 946       delete_insn (curr_insn);
 947     }
 948
 949   free (is_insn_merge_attempted);
 950   VEC_free (rtx, heap, zeinsn_list);
 951   VEC_free (rtx, heap, zeinsn_del_list);
 952
 953   if (dump_file && num_ze_opportunities > 0)
 954     fprintf (dump_file, "\n %s : num_zee_opportunities = %lld "
 955                         "num_realized = %lld \n",
 956                         current_function_name (),
 957                         num_ze_opportunities, num_realized);
 958
 959   df_finish_pass (false);
 960   return 0;
 961 }
 962
 963 /* Find and remove redundant zero extensions.  */
 964
 965 static unsigned int
 966 rest_of_handle_zee (void)
 967 {
 968   timevar_push (TV_ZEE);
 969   find_and_remove_ze ();
 970   timevar_pop (TV_ZEE);
 971   return 0;
 972 }
 973
 974 /* Run zee pass when flag_zee is set at optimization level > 0.  */
 975
 976 static bool
 977 gate_handle_zee (void)
 978 {
 979   return (optimize > 0 && flag_zee);
 980 }
 981
 982 struct rtl_opt_pass pass_implicit_zee =
 983 {
 984  {
 985   RTL_PASS,
 986   "zee",                                /* name */
 987   gate_handle_zee,                      /* gate */
 988   rest_of_handle_zee,                   /* execute */
 989   NULL,                                 /* sub */
 990   NULL,                                 /* next */
 991   0,                                    /* static_pass_number */
 992   TV_ZEE,                               /* tv_id */
 993   0,                                    /* properties_required */
 994   0,                                    /* properties_provided */
 995   0,                                    /* properties_destroyed */
 996   0,                                    /* todo_flags_start */
 997   TODO_ggc_collect |
 998   TODO_dump_func |
 999   TODO_verify_rtl_sharing,              /* todo_flags_finish */
1000  }
1001 };