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 "real.h"
 197 #include "toplev.h"
 198 #include "target.h"
 199 #include "timevar.h"
 200 #include "optabs.h"
 201 #include "insn-codes.h"
 202 #include "rtlhooks-def.h"
 203 /* Include output.h for dump_file.  */
 204 #include "output.h"
 205 #include "params.h"
 206 #include "timevar.h"
 207 #include "tree-pass.h"
 208 #include "df.h"
 209 #include "cgraph.h"
 210
 211 /* This says if a register is newly created for the purpose of
 212    zero-extension.  */
 213
 214 enum insn_merge_code
 215 {
 216   MERGE_NOT_ATTEMPTED = 0,
 217   MERGE_SUCCESS
 218 };
 219
 220 /* This says if a INSN UID or its definition has already been merged
 221    with a zero-extend or not.  */
 222
 223 static enum insn_merge_code *is_insn_merge_attempted;
 224 static int max_insn_uid;
 225
 226 /* Returns the merge code status for INSN.  */
 227
 228 static enum insn_merge_code
 229 get_insn_status (rtx insn)
 230 {
 231   gcc_assert (INSN_UID (insn) < max_insn_uid);
 232   return is_insn_merge_attempted[INSN_UID (insn)];
 233 }
 234
 235 /* Sets the merge code status of INSN to CODE.  */
 236
 237 static void
 238 set_insn_status (rtx insn, enum insn_merge_code code)
 239 {
 240   gcc_assert (INSN_UID (insn) < max_insn_uid);
 241   is_insn_merge_attempted[INSN_UID (insn)] = code;
 242 }
 243
 244 /* Check to see if this zero-extend matches a pattern
 245    that could be eliminated.  This is called via
 246    for_each_rtx in function find_and_remove_ze.  */
 247
 248 static int
 249 is_set_with_extension_DI (rtx *expr, void *data)
 250 {
 251   /* Looking only for patterns of the type :
 252      SET (REG:DI X) (ZERO_EXTEND (REG:SI x))
 253    */
 254
 255   if (GET_CODE (*expr) == SET
 256       && GET_MODE (SET_DEST (*expr)) == DImode
 257       && GET_CODE (SET_DEST (*expr)) == REG
 258       && GET_CODE (SET_SRC (*expr)) == ZERO_EXTEND
 259       && GET_CODE (XEXP (SET_SRC (*expr),0)) == REG
 260       && GET_MODE (XEXP (SET_SRC (*expr),0)) == SImode
 261       && REGNO (SET_DEST (*expr)) == REGNO (XEXP (SET_SRC (*expr),0)))
 262         {
 263           *(rtx **)(data) = expr;
 264           return 1;
 265         }
 266   return 0;
 267 }
 268
 269 /* Given a insn (CURR_INSN) and a pointer to the SET rtx (ORIG_SET)
 270    that needs to be modified, this code modifies the SET rtx to a
 271    new SET rtx that zero_extends the right hand expression into a DImode
 272    register (NEWREG) on the left hand side.  Note that multiple
 273    assumptions are made about the nature of the set that needs
 274    to be true for this to work and is called from merge_def_and_ze.
 275
 276    Original :
 277    (set (reg:SI a) (expression))
 278
 279    Transform :
 280    (set (reg:DI a) (zero_extend (expression)))
 281
 282    Special Cases :
 283    If the expression is a constant or another zero_extend directly
 284    assign it to the DI mode register.  */
 285
 286 static bool
 287 combine_set_zero_extend (rtx curr_insn, rtx *orig_set, rtx newreg)
 288 {
 289   rtx temp_extension, simplified_temp_extension, new_set, new_const_int;
 290   rtx orig_src;
 291   HOST_WIDE_INT val;
 292   unsigned int mask, delta_width;
 293
 294   /* Change the SET rtx and validate it.  */
 295   orig_src = SET_SRC (*orig_set);
 296   new_set = NULL_RTX;
 297
 298   /* The right hand side can also be VOIDmode.  These cases have to be
 299      handled differently.  */
 300
 301   if (GET_MODE (orig_src) != SImode)
 302     {
 303       /* Merge constants by directly moving the constant into the
 304          DImode register under some conditions.  */
 305
 306       if (GET_CODE (orig_src) == CONST_INT
 307           && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (SImode))
 308         {
 309           if (INTVAL (orig_src) >= 0)
 310             new_set = gen_rtx_SET (VOIDmode, newreg, orig_src);
 311           else if (INTVAL (orig_src) < 0)
 312             {
 313               /* Zero-extending a negative SImode integer into DImode
 314                  makes it a positive integer.  Convert the given negative
 315                  integer into the appropriate integer when zero-extended.  */
 316
 317               delta_width = HOST_BITS_PER_WIDE_INT - GET_MODE_BITSIZE (SImode);
 318               mask = (~(unsigned HOST_WIDE_INT) 0) >> delta_width;
 319               val = INTVAL (orig_src);
 320               val = val & mask;
 321               new_const_int = gen_rtx_CONST_INT (VOIDmode, val);
 322               new_set = gen_rtx_SET (VOIDmode, newreg, new_const_int);
 323             }
 324           else
 325             return false;
 326         }
 327       else
 328         {
 329           /* This is mostly due to a call insn that should not be
 330              optimized.  */
 331
 332           return false;
 333         }
 334     }
 335   else if (GET_CODE (orig_src) == ZERO_EXTEND)
 336     {
 337       /* Here a zero-extend is used to get to SI. Why not make it
 338          all the  way till DI.  */
 339
 340       temp_extension = gen_rtx_ZERO_EXTEND (DImode, XEXP (orig_src, 0));
 341       simplified_temp_extension = simplify_rtx (temp_extension);
 342       if (simplified_temp_extension)
 343         temp_extension = simplified_temp_extension;
 344       new_set = gen_rtx_SET (VOIDmode, newreg, temp_extension);
 345     }
 346   else if (GET_CODE (orig_src) == IF_THEN_ELSE)
 347     {
 348       /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
 349          in general, IF_THEN_ELSE should not be combined.  */
 350
 351       return false;
 352     }
 353   else
 354     {
 355       /* This is the normal case we expect.  */
 356
 357       temp_extension = gen_rtx_ZERO_EXTEND (DImode, orig_src);
 358       simplified_temp_extension = simplify_rtx (temp_extension);
 359       if (simplified_temp_extension)
 360         temp_extension = simplified_temp_extension;
 361       new_set = gen_rtx_SET (VOIDmode, newreg, temp_extension);
 362     }
 363
 364   gcc_assert (new_set != NULL_RTX);
 365
 366   /* This change is a part of a group of changes. Hence,
 367      validate_change will not try to commit the change.  */
 368
 369   if (validate_change (curr_insn, orig_set, new_set, true))
 370     {
 371       if (dump_file)
 372         {
 373           fprintf (dump_file, "Merged Instruction with ZERO_EXTEND:\n");
 374           print_rtl_single (dump_file, curr_insn);
 375         }
 376       return true;
 377     }
 378   return false;
 379 }
 380
 381 /* This returns the DI mode for the SI register REG_SI.  */
 382
 383 static rtx
 384 get_reg_di (rtx reg_si)
 385 {
 386   rtx newreg;
 387
 388   newreg = gen_rtx_REG (DImode, REGNO (reg_si));
 389   gcc_assert (newreg);
 390   return newreg;
 391 }
 392
 393 /* Treat if_then_else insns, where the operands of both branches
 394    are registers, as copies. For instance,
 395    Original :
 396    (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
 397    Transformed :
 398    (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
 399    DEF_INSN is the if_then_else insn.  */
 400
 401 static bool
 402 transform_ifelse (rtx def_insn)
 403 {
 404   rtx set_insn = PATTERN (def_insn);
 405   rtx srcreg, dstreg, srcreg2;
 406   rtx map_srcreg, map_dstreg, map_srcreg2;
 407   rtx ifexpr;
 408   rtx cond;
 409   rtx new_set;
 410
 411   gcc_assert (GET_CODE (set_insn) == SET);
 412   cond = XEXP (SET_SRC (set_insn), 0);
 413   dstreg = SET_DEST (set_insn);
 414   srcreg = XEXP (SET_SRC (set_insn), 1);
 415   srcreg2 = XEXP (SET_SRC (set_insn), 2);
 416   map_srcreg = get_reg_di (srcreg);
 417   map_srcreg2 = get_reg_di (srcreg2);
 418   map_dstreg = get_reg_di (dstreg);
 419   ifexpr = gen_rtx_IF_THEN_ELSE (DImode, cond, map_srcreg, map_srcreg2);
 420   new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
 421
 422   if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
 423     {
 424       if (dump_file)
 425         {
 426           fprintf (dump_file, "Cond_Move Instruction's mode extended :\n");
 427           print_rtl_single (dump_file, def_insn);
 428         }
 429       return true;
 430     }
 431   else
 432     return false;
 433 }
 434
 435 /* Function to get all the immediate definitions of an instruction.
 436    The reaching definitions are desired for WHICH_REG used in
 437    CURR_INSN.  This function returns 0 if there was an error getting
 438    a definition.  Upon success, this function returns the number of
 439    definitions and stores the definitions in DEST.  */
 440
 441 static int
 442 get_defs (rtx curr_insn, rtx which_reg, VEC (rtx,heap) **dest)
 443 {
 444   df_ref reg_info, *defs;
 445   struct df_link *def_chain;
 446   int n_refs = 0;
 447
 448   defs = DF_INSN_USES (curr_insn);
 449   reg_info = NULL;
 450
 451   while (*defs)
 452     {
 453       reg_info = *defs;
 454       if (GET_CODE (DF_REF_REG (reg_info)) == SUBREG)
 455         return 0;
 456       if (REGNO (DF_REF_REG (reg_info)) == REGNO (which_reg))
 457         break;
 458       defs++;
 459     }
 460
 461   gcc_assert (reg_info != NULL && defs != NULL);
 462   def_chain = DF_REF_CHAIN (reg_info);
 463
 464   while (def_chain)
 465     {
 466       /* Problem getting some definition for this instruction.  */
 467
 468       if (def_chain->ref == NULL)
 469         return 0;
 470       if (DF_REF_INSN_INFO (def_chain->ref) == NULL)
 471         return 0;
 472       def_chain = def_chain->next;
 473     }
 474
 475   def_chain = DF_REF_CHAIN (reg_info);
 476
 477   if (dest == NULL)
 478     return 1;
 479
 480   while (def_chain)
 481     {
 482       VEC_safe_push (rtx, heap, *dest, DF_REF_INSN (def_chain->ref));
 483       def_chain = def_chain->next;
 484       n_refs++;
 485     }
 486   return n_refs;
 487 }
 488
 489 /* rtx function to check if this SET insn, EXPR, is a conditional copy insn :
 490    (set (reg:SI a ) (IF_THEN_ELSE (cond) (reg:SI b) (reg:SI c)))
 491    Called from is_insn_cond_copy.  DATA stores the two registers on each
 492    side of the condition.  */
 493
 494 static int
 495 is_this_a_cmove (rtx expr, void *data)
 496 {
 497   /* Check for conditional (if-then-else) copy.  */
 498
 499   if (GET_CODE (expr) == SET
 500       && GET_CODE (SET_DEST (expr)) == REG
 501       && GET_MODE (SET_DEST (expr)) == SImode
 502       && GET_CODE (SET_SRC (expr))  == IF_THEN_ELSE
 503       && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
 504       && GET_MODE (XEXP (SET_SRC (expr), 1)) == SImode
 505       && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG
 506       && GET_MODE (XEXP (SET_SRC (expr), 2)) == SImode)
 507     {
 508       ((rtx *)data)[0] = XEXP (SET_SRC (expr), 1);
 509       ((rtx *)data)[1] = XEXP (SET_SRC (expr), 2);
 510       return 1;
 511     }
 512   return 0;
 513 }
 514
 515 /* This returns 1 if it found
 516    (SET (reg:SI REGNO (def_reg)) (if_then_else (cond) (REG:SI x1) (REG:SI x2)))
 517    in the DEF_INSN pattern.  It stores the x1 and x2 in COPY_REG_1
 518    and COPY_REG_2.  */
 519
 520 static int
 521 is_insn_cond_copy (rtx def_insn, rtx *copy_reg_1, rtx *copy_reg_2)
 522 {
 523   int type;
 524   rtx set_expr;
 525   rtx srcreg[2];
 526
 527   srcreg[0] = NULL_RTX;
 528   srcreg[1] = NULL_RTX;
 529
 530   set_expr = single_set (def_insn);
 531
 532   if (set_expr == NULL_RTX)
 533     return 0;
 534
 535   type = is_this_a_cmove (set_expr, (void *) srcreg);
 536
 537   if (type)
 538     {
 539       *copy_reg_1 = srcreg[0];
 540       *copy_reg_2 = srcreg[1];
 541       return type;
 542     }
 543
 544   return 0;
 545 }
 546
 547 /* Reaching Definitions of the zero-extended register could be conditional
 548    copies or regular definitions.  This function separates the two types into
 549    two lists, DEFS_LIST and COPIES_LIST.  This is necessary because, if a
 550    reaching definition is a conditional copy, combining the zero_extend with
 551    this definition is wrong.  Conditional copies are merged by transitively
 552    merging its definitions.  The defs_list is populated with all the reaching
 553    definitions of the zero-extension instruction (ZERO_EXTEND_INSN) which must
 554    be merged with a zero_extend.  The copies_list contains all the conditional
 555    moves that will later be extended into a DI mode conditonal move if all the
 556    merges are successful.  The function returns false when there is a failure
 557    in getting some definitions, like that of parameters.  It returns 1 upon
 558    success, 0 upon failure and 2 when all definitions of the ZERO_EXTEND_INSN
 559    were merged previously.  */
 560
 561 static int
 562 make_defs_and_copies_lists (rtx zero_extend_insn, rtx set_pat,
 563                             VEC (rtx,heap) **defs_list,
 564                             VEC (rtx,heap) **copies_list)
 565 {
 566   bool *is_insn_visited;
 567   VEC (rtx,heap) *work_list;
 568   rtx srcreg, copy_reg_1, copy_reg_2;
 569   rtx def_insn;
 570   int n_defs = 0;
 571   int vec_index = 0;
 572   int n_worklist = 0;
 573   int i, is_copy;
 574
 575   srcreg = XEXP (SET_SRC (set_pat), 0);
 576   work_list = VEC_alloc (rtx, heap, 8);
 577
 578   /* Initialize the Work List */
 579   n_worklist = get_defs (zero_extend_insn, srcreg, &work_list);
 580
 581   if (n_worklist == 0)
 582     {
 583       VEC_free (rtx, heap, work_list);
 584       /* The number of defs being equal to zero can only imply that all of its
 585          definitions have been previously merged.  */
 586       return 2;
 587     }
 588
 589   is_insn_visited = XNEWVEC (bool, max_insn_uid);
 590
 591   for (i = 0; i < max_insn_uid; i++)
 592     is_insn_visited[i] = false;
 593
 594
 595   /* Perform transitive closure for conditional copies.  */
 596   while (n_worklist > vec_index)
 597     {
 598       def_insn = VEC_index (rtx, work_list, vec_index);
 599       gcc_assert (INSN_UID (def_insn) < max_insn_uid);
 600
 601       if (is_insn_visited[INSN_UID (def_insn)])
 602         {
 603           vec_index++;
 604           continue;
 605         }
 606
 607       is_insn_visited[INSN_UID (def_insn)] = true;
 608       copy_reg_1 = copy_reg_2 = NULL_RTX;
 609       is_copy = is_insn_cond_copy (def_insn, &copy_reg_1, &copy_reg_2);
 610       if (is_copy)
 611         {
 612           gcc_assert (copy_reg_1 && copy_reg_2);
 613
 614           /* Push it into the copy list first.  */
 615
 616           VEC_safe_push (rtx, heap, *copies_list, def_insn);
 617
 618           /* Perform transitive closure here */
 619
 620           n_defs = get_defs (def_insn, copy_reg_1, &work_list);
 621
 622           if (n_defs == 0)
 623             {
 624               VEC_free (rtx, heap, work_list);
 625               XDELETEVEC (is_insn_visited);
 626               return 0;
 627             }
 628           n_worklist += n_defs;
 629
 630           n_defs = get_defs (def_insn, copy_reg_2, &work_list);
 631           if (n_defs == 0)
 632             {
 633               VEC_free (rtx, heap, work_list);
 634               XDELETEVEC (is_insn_visited);
 635               return 0;
 636             }
 637           n_worklist += n_defs;
 638         }
 639       else
 640         {
 641           VEC_safe_push (rtx, heap, *defs_list, def_insn);
 642         }
 643       vec_index++;
 644     }
 645
 646   VEC_free (rtx, heap, work_list);
 647   XDELETEVEC (is_insn_visited);
 648   return 1;
 649 }
 650
 651 /* Merge the DEF_INSN with a zero-extend.  Calls combine_set_zero_extend
 652    on the SET pattern.  */
 653
 654 static bool
 655 merge_def_and_ze (rtx def_insn)
 656 {
 657   enum rtx_code code;
 658   rtx setreg;
 659   rtx *sub_rtx;
 660   rtx s_expr;
 661   int i;
 662
 663   code = GET_CODE (PATTERN (def_insn));
 664   sub_rtx = NULL;
 665
 666   if (code == PARALLEL)
 667     {
 668       for (i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
 669         {
 670           s_expr = XVECEXP (PATTERN (def_insn), 0, i);
 671           if (GET_CODE (s_expr) != SET)
 672             continue;
 673
 674           if (sub_rtx == NULL)
 675             sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
 676           else
 677             {
 678               /* PARALLEL with multiple SETs.  */
 679               return false;
 680             }
 681         }
 682     }
 683   else if (code == SET)
 684     sub_rtx = &PATTERN (def_insn);
 685   else
 686     {
 687       /* It is not a PARALLEL or a SET, what could it be ? */
 688       return false;
 689     }
 690
 691   gcc_assert (sub_rtx != NULL);
 692
 693   if (GET_CODE (SET_DEST (*sub_rtx)) == REG
 694       && GET_MODE (SET_DEST (*sub_rtx)) == SImode)
 695     {
 696       setreg = get_reg_di (SET_DEST (*sub_rtx));
 697       return combine_set_zero_extend (def_insn, sub_rtx, setreg);
 698     }
 699   else
 700     return false;
 701   return true;
 702 }
 703
 704 /* This function goes through all reaching defs of the source
 705    of the zero extension instruction (ZERO_EXTEND_INSN) and
 706    tries to combine the zero extension with the definition
 707    instruction.  The changes are made as a group so that even
 708    if one definition cannot be merged, all reaching definitions
 709    end up not being merged. When a conditional copy is encountered,
 710    merging is attempted transitively on its definitions.  It returns
 711    true upon success and false upon failure.  */
 712
 713 static bool
 714 combine_reaching_defs (rtx zero_extend_insn, rtx set_pat)
 715 {
 716   rtx def_insn;
 717   bool merge_successful = true;
 718   int i;
 719   int defs_ix;
 720   int outcome;
 721
 722   /* To store the definitions that have been merged.  */
 723
 724   VEC (rtx, heap) *defs_list, *copies_list, *vec;
 725   enum insn_merge_code merge_code;
 726
 727   defs_list = VEC_alloc (rtx, heap, 8);
 728   copies_list = VEC_alloc (rtx, heap, 8);
 729
 730   outcome = make_defs_and_copies_lists (zero_extend_insn,
 731                                         set_pat, &defs_list, &copies_list);
 732
 733   /* outcome == 2 implies that all the definitions for this zero_extend were
 734      merged while previously when handling other zero_extends.  */
 735
 736   if (outcome == 2)
 737     {
 738       VEC_free (rtx, heap, defs_list);
 739       VEC_free (rtx, heap, copies_list);
 740       if (dump_file)
 741         fprintf (dump_file, "All definitions have been merged previously...\n");
 742       return true;
 743     }
 744
 745   if (outcome == 0)
 746     {
 747       VEC_free (rtx, heap, defs_list);
 748       VEC_free (rtx, heap, copies_list);
 749       return false;
 750     }
 751
 752   merge_successful = true;
 753
 754   /* Go through the defs vector and try to merge all the definitions
 755      in this vector.  */
 756
 757   vec = VEC_alloc (rtx, heap, 8);
 758   for (defs_ix = 0; VEC_iterate (rtx, defs_list, defs_ix, def_insn); defs_ix++)
 759     {
 760       merge_code = get_insn_status (def_insn);
 761       gcc_assert (merge_code == MERGE_NOT_ATTEMPTED);
 762
 763       if (merge_def_and_ze (def_insn))
 764         VEC_safe_push (rtx, heap, vec, def_insn);
 765       else
 766         {
 767           merge_successful = false;
 768           break;
 769         }
 770     }
 771
 772   /* Now go through the conditional copies vector and try to merge all
 773      the copies in this vector.  */
 774
 775   if (merge_successful)
 776     {
 777       for (i = 0; VEC_iterate (rtx, copies_list, i, def_insn); i++)
 778         {
 779           if (transform_ifelse (def_insn))
 780             {
 781               VEC_safe_push (rtx, heap, vec, def_insn);
 782             }
 783           else
 784             {
 785               merge_successful = false;
 786               break;
 787             }
 788         }
 789     }
 790
 791   if (merge_successful)
 792     {
 793       /* Commit the changes here if possible */
 794       /* XXX : Now, it is an all or nothing scenario.  Even if one definition
 795          cannot be merged we totally bail.  In future, allow zero-extensions to
 796          be partially eliminated along those paths where the definitions could
 797          be merged.  */
 798
 799       if (apply_change_group ())
 800         {
 801           if (dump_file)
 802             fprintf (dump_file, "All merges were successful ....\n");
 803
 804           for (i = 0; VEC_iterate (rtx, vec, i, def_insn); i++)
 805             {
 806               set_insn_status (def_insn, MERGE_SUCCESS);
 807             }
 808
 809           VEC_free (rtx, heap, vec);
 810           VEC_free (rtx, heap, defs_list);
 811           VEC_free (rtx, heap, copies_list);
 812           return true;
 813         }
 814       else
 815         {
 816           /* Changes need not be cancelled explicitly as apply_change_group ()
 817              does it.   Print list of definitions in the dump_file for debug
 818              purposes.  This zero-extension cannot be deleted.  */
 819
 820           if (dump_file)
 821             {
 822               for (i = 0; VEC_iterate (rtx, vec, i, def_insn); i++)
 823                 {
 824                   fprintf (dump_file, " Ummergable definitions : \n");
 825                   print_rtl_single (dump_file, def_insn);
 826                 }
 827             }
 828         }
 829     }
 830   else
 831     {
 832       /* Cancel any changes that have been made so far.  */
 833       cancel_changes (0);
 834     }
 835
 836   VEC_free (rtx, heap, vec);
 837   VEC_free (rtx, heap, defs_list);
 838   VEC_free (rtx, heap, copies_list);
 839   return false;
 840 }
 841
 842 /* Goes through the instruction stream looking for zero-extends.  If the zero
 843    extension instruction has atleast one def it adds it to a list of possible
 844    candidates for deletion.  It returns the list of candidates.  */
 845
 846 static VEC (rtx,heap)*
 847 find_removable_zero_extends (void)
 848 {
 849   VEC (rtx, heap) *zeinsn_list;
 850   basic_block curr_block;
 851   rtx curr_insn;
 852   rtx *set_insn;
 853   rtx which_reg;
 854   int type ;
 855   int has_defs;
 856
 857   zeinsn_list = VEC_alloc (rtx, heap, 8);
 858   FOR_EACH_BB (curr_block)
 859     {
 860       FOR_BB_INSNS (curr_block, curr_insn)
 861         {
 862           if (!INSN_P (curr_insn))
 863             continue;
 864
 865           type = for_each_rtx (&PATTERN (curr_insn),
 866                                is_set_with_extension_DI,
 867                                (void *)&set_insn);
 868
 869           if (!type)
 870             continue;
 871
 872           which_reg = XEXP (SET_SRC (*set_insn), 0);
 873           has_defs = get_defs (curr_insn, which_reg, NULL);
 874           if (has_defs)
 875             VEC_safe_push (rtx, heap, zeinsn_list, curr_insn);
 876           else if (dump_file)
 877             {
 878               fprintf (dump_file, "Cannot eliminate zero extension : \n");
 879               print_rtl_single (dump_file, curr_insn);
 880               fprintf (dump_file,
 881                        "This has no defs. Could be extending parameters.\n");
 882             }
 883         }
 884     }
 885   return zeinsn_list;
 886 }
 887
 888 /* This is the main function that checks the insn stream for redundant
 889    zero extensions and tries to remove them if possible.  */
 890
 891 static unsigned int
 892 find_and_remove_ze (void)
 893 {
 894   rtx curr_insn = NULL_RTX;
 895   int i;
 896   int ix;
 897   long long num_realized = 0;
 898   long long num_ze_opportunities = 0;
 899   VEC (rtx, heap) *zeinsn_list;
 900   VEC (rtx, heap) *zeinsn_del_list;
 901
 902   /* Construct DU chain to get all reaching definitions of each
 903      zero-extension instruction.  */
 904
 905   df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
 906   df_analyze ();
 907
 908   max_insn_uid = get_max_uid ();
 909
 910   is_insn_merge_attempted = XNEWVEC (enum insn_merge_code,
 911                                      sizeof (enum insn_merge_code)* max_insn_uid);
 912
 913   for (i = 0; i < max_insn_uid; i++)
 914     {
 915       is_insn_merge_attempted[i] = MERGE_NOT_ATTEMPTED;
 916     }
 917
 918   num_ze_opportunities = num_realized = 0;
 919
 920   zeinsn_del_list = VEC_alloc (rtx, heap, 4);
 921
 922   zeinsn_list = find_removable_zero_extends ();
 923
 924   for (ix = 0; VEC_iterate (rtx, zeinsn_list, ix, curr_insn); ix++)
 925     {
 926       num_ze_opportunities++;
 927       /* Try to combine the zero-extends with the definition here.  */
 928
 929       if (dump_file)
 930         {
 931           fprintf (dump_file, "Trying to eliminate zero extension : \n");
 932           print_rtl_single (dump_file, curr_insn);
 933         }
 934
 935       if (combine_reaching_defs (curr_insn, PATTERN (curr_insn)))
 936         {
 937           if (dump_file)
 938             fprintf (dump_file, "Eliminated the zero extension...\n");
 939           num_realized++;
 940           VEC_safe_push (rtx, heap, zeinsn_del_list, curr_insn);
 941         }
 942     }
 943
 944   /* Delete all useless zero extensions here in one sweep.  */
 945   for (ix = 0; VEC_iterate (rtx, zeinsn_del_list, ix, curr_insn); ix++)
 946     {
 947       delete_insn (curr_insn);
 948     }
 949
 950   free (is_insn_merge_attempted);
 951   VEC_free (rtx, heap, zeinsn_list);
 952   VEC_free (rtx, heap, zeinsn_del_list);
 953
 954   if (dump_file && num_ze_opportunities > 0)
 955     fprintf (dump_file, "\n %s : num_zee_opportunities = %lld "
 956                         "num_realized = %lld \n",
 957                         current_function_name (),
 958                         num_ze_opportunities, num_realized);
 959
 960   df_finish_pass (false);
 961   return 0;
 962 }
 963
 964 /* Find and remove redundant zero extensions.  */
 965
 966 static unsigned int
 967 rest_of_handle_zee (void)
 968 {
 969   timevar_push (TV_ZEE);
 970   find_and_remove_ze ();
 971   timevar_pop (TV_ZEE);
 972   return 0;
 973 }
 974
 975 /* Run zee pass when flag_zee is set at optimization level > 0.  */
 976
 977 static bool
 978 gate_handle_zee (void)
 979 {
 980   return (optimize > 0 && flag_zee);
 981 }
 982
 983 struct rtl_opt_pass pass_implicit_zee =
 984 {
 985  {
 986   RTL_PASS,
 987   "zee",                                /* name */
 988   gate_handle_zee,                      /* gate */
 989   rest_of_handle_zee,                   /* execute */
 990   NULL,                                 /* sub */
 991   NULL,                                 /* next */
 992   0,                                    /* static_pass_number */
 993   TV_ZEE,                               /* tv_id */
 994   0,                                    /* properties_required */
 995   0,                                    /* properties_provided */
 996   0,                                    /* properties_destroyed */
 997   0,                                    /* todo_flags_start */
 998   TODO_ggc_collect |
 999   TODO_dump_func |
1000   TODO_verify_rtl_sharing,              /* todo_flags_finish */
1001  }
1002 };