Subversion Repositories openrisc_me

/* Sign extension elimination optimization for GNU compiler.

   Copyright (C) 2005, 2007 Free Software Foundation, Inc.

   Contributed by Leehod Baruch <leehod@il.ibm.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

-Software Foundation; either version 3, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.

Problem description:

--------------------

In order to support 32bit computations on a 64bit machine, sign

extension instructions are generated to ensure the correctness of

the computation.

A possible policy (as currently implemented) is to generate a sign

extension right after each 32bit computation.

Depending on the instruction set of the architecture, some of these

sign extension instructions may be redundant.

There are two cases in which the extension may be redundant:

Case1:

The instruction that uses the 64bit operands that are sign

extended has a dual mode that works with 32bit operands.

For example:

  int32 a, b;

  a = ....             -->      a = ....

  a = sign extend a    -->

  b = ....             -->      b = ....

  b = sign extend a    -->

                       -->

  cmpd a, b            -->      cmpw a, b  //half word compare

Case2:

The instruction that defines the 64bit operand (which is later sign

extended) has a dual mode that defines and sign-extends simultaneously

a 32bit operand.  For example:

  int32 a;

  ld a               -->   lwa a   // load half word and sign extend

  a = sign extend a  -->

                     -->

  return a           -->   return a

General idea for solution:

--------------------------

First, try to merge the sign extension with the instruction that

defines the source of the extension and (separately) with the

instructions that uses the extended result.  By doing this, both cases

of redundancies (as described above) will be eliminated.

Then, use partial redundancy elimination to place the non redundant

ones at optimal placements.

Implementation by example:

--------------------------

Note: The instruction stream is not changed till the last phase.

Phase 0: Initial code, as currently generated by gcc.

                         def1           def3

                         se1     def2    se3

                          | \     |     / |

                          |  \    |    /  |

                          |   \   |   /   |

                          |    \  |  /    |

                          |     \ | /     |

                          |      \|/      |

                        use1    use2     use3

                                         use4

def1 + se1:

set ((reg:SI 10) (..def1rhs..))

set ((reg:DI 100) (sign_extend:DI (reg:SI 10)))

def2:

set ((reg:DI 100) (const_int 7))

def3 + se3:

set ((reg:SI 20) (..def3rhs..))

set ((reg:DI 100) (sign_extend:DI (reg:SI 20)))

use1:

set ((reg:CC...) (compare:CC (reg:DI 100) (...)))

use2, use3, use4:

set ((...) (reg:DI 100))

Phase 1: Propagate extensions to uses.

                         def1           def3

                         se1     def2    se3

                          | \     |     / |

                          |  \    |    /  |

                          |   \   |   /   |

                          |    \  |  /    |

                          |     \ | /     |

                          |      \|/      |

                         se      se      se

                        use1    use2     use3

                                         se

                                         use4

From here, all of the subregs are lowpart !

def1, def2, def3: No change.

use1:

set ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))

set ((reg:CC...) (compare:CC (reg:DI 100) (...)))

use2, use3, use4:

set ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))

set ((...) (reg:DI 100))

Phase 2: Merge and eliminate locally redundant extensions.

                        *def1    def2   *def3

                  [se removed]    se     se3

                          | \     |     / |

                          |  \    |    /  |

                          |   \   |   /   |

                          |    \  |  /    |

                          |     \ | /     |

                          |      \|/      |

                  [se removed]   se       se

                        *use1   use2     use3

                                      [se removed]

                                         use4

The instructions that were changed at this phase are marked with

asterisk.

*def1: Merge failed.

       Remove the sign extension instruction, modify def1 and

       insert a move instruction to assure to correctness of the code.

set ((subreg:SI (reg:DI 100)) (..def1rhs..))

set ((reg:SI 10) (subreg:SI (reg:DI 100)))

def2 + se: There is no need for merge.

           Def2 is not changed but a sign extension instruction is

           created.

set ((reg:DI 100) (const_int 7))

set ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))

*def3 + se3: Merge succeeded.

set ((reg:DI 100) (sign_extend:DI (..def3rhs..)))

set ((reg:SI 20) (reg:DI 100))

set ((reg:DI 100) (sign_extend:DI (reg:SI 20)))

(The extension instruction is the original one).

*use1: Merge succeeded.  Remove the sign extension instruction.

set ((reg:CC...)

     (compare:CC (subreg:SI (reg:DI 100)) (...)))

use2, use3: Merge failed.  No change.

use4: The extension is locally redundant, therefore it is eliminated

      at this point.

Phase 3: Eliminate globally redundant extensions.

Following the LCM output:

                         def1    def2    def3

                                  se     se3

                          | \     |     / |

                          |  \    |    /  |

                          |   se  |   /   |

                          |    \  |  /    |

                          |     \ | /     |

                          |      \|/      |

                                [ses removed]

                         use1   use2     use3

                                         use4

se:

set ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))

se3:

set ((reg:DI 100) (sign_extend:DI (reg:SI 20)))

Phase 4: Commit changes to the insn stream.

   def1            def3                 *def1    def2   *def3

    se1    def2    se3              [se removed]       [se removed]

    | \     |     / |                     | \     |     / |

    |  \    |    /  |      ------>        |  \    |    /  |

    |   \   |   /   |      ------>        |   se  |   /   |

    |    \  |  /    |                     |    \  |  /    |

    |     \ | /     |                     |     \ | /     |

    |      \|/      |                     |      \|/      |

   use1    use2    use3                  *use1   use2    use3

                   use4                                  use4

The instructions that were changed during the whole optimization are

marked with asterisk.

The result:

def1 + se1:

[  set ((reg:SI 10) (..def1rhs..))                   ]   - Deleted

[  set ((reg:DI 100) (sign_extend:DI (reg:SI 10)))   ]   - Deleted

set ((subreg:SI (reg:DI 100)) (..def3rhs..))             - Inserted

set ((reg:SI 10) (subreg:SI (reg:DI 100)))               - Inserted

def2:

set ((reg:DI 100) (const_int 7))                         - No change

def3 + se3:

[  set ((reg:SI 20) (..def3rhs..))                   ]   - Deleted

[  set ((reg:DI 100) (sign_extend:DI (reg:SI 20)))   ]   - Deleted

set ((reg:DI 100) (sign_extend:DI (..def3rhs..)))        - Inserted

set ((reg:SI 20) (reg:DI 100))                           - Inserted

use1:

[  set ((reg:CC...) (compare:CC (reg:DI 100) (...))) ]   - Deleted

set ((reg:CC...)                                         - Inserted

     (compare:CC (subreg:SI (reg:DI 100)) (...)))

use2, use3, use4:

set ((...) (reg:DI 100))                                 - No change

se:                                                      - Inserted

set ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))

Note: Most of the simple move instructions that were inserted will be

      trivially dead and therefore eliminated.

The implementation outline:

---------------------------

Some definitions:

   A web is RELEVANT if at the end of phase 1, his leader's

     relevancy is {ZERO, SIGN}_EXTENDED_DEF.  The source_mode of

     the web is the source_mode of his leader.

   A definition is a candidate for the optimization if it is part

     of a RELEVANT web and his local source_mode is not narrower

     then the source_mode of its web.

   A use is a candidate for the optimization if it is part of a

     RELEVANT web.

   A simple explicit extension is a single set instruction that

     extends a register (or a subregister) to a register (or

     subregister).

   A complex explicit extension is an explicit extension instruction

     that is not simple.

   A def extension is a simple explicit extension that is

     also a candidate for the optimization.  This extension is part

     of the instruction stream, it is not generated by this

     optimization.

   A use extension is a simple explicit extension that is generated

     and stored for candidate use during this optimization.  It is

     not emitted to the instruction stream till the last phase of

     the optimization.

   A reference is an instruction that satisfy at least on of these

     criteria:

     - It contains a definition with EXTENDED_DEF relevancy in a RELEVANT web.

     - It is followed by a def extension.

     - It contains a candidate use.

Phase 1: Propagate extensions to uses.

  In this phase, we find candidate extensions for the optimization

  and we generate (but not emit) proper extensions "right before the

  uses".

  a. Build a DF object.

  b. Traverse over all the instructions that contains a definition

     and set their local relevancy and local source_mode like this:

     - If the instruction is a simple explicit extension instruction,

       mark it as {ZERO, SIGN}_EXTENDED_DEF according to the extension

       type and mark its source_mode to be the mode of the quantity

       that is been extended.

     - Otherwise, If the instruction has an implicit extension,

       which means that its high part is an extension of its low part,

       or if it is a complicated explicit extension, mark it as

       EXTENDED_DEF and set its source_mode to be the narrowest

       mode that is been extended in the instruction.

  c. Traverse over all the instructions that contains a use and set

     their local relevancy to RELEVANT_USE (except for few corner

     cases).

  d. Produce the web.  During union of two entries, update the

     relevancy and source_mode of the leader.  There are two major

     guide lines for this update:

     - If one of the entries is NOT_RELEVANT, mark the leader

       NOT_RELEVANT.

     - If one is ZERO_EXTENDED_DEF and the other is SIGN_EXTENDED_DEF

       (or vice versa) mark the leader as NOT_RELEVANT.  We don't

       handle this kind of mixed webs.

     (For more details about this update process,

      see see_update_leader_extra_info ()).

  e. Generate uses extensions according to the relevancy and

     source_mode of the webs.

Phase 2: Merge and eliminate locally redundant extensions.

  In this phase, we try to merge def extensions and use

  extensions with their references, and eliminate redundant extensions

  in the same basic block.

  Traverse over all the references.  Do this in basic block number and

  luid number forward order.

  For each reference do:

    a. Peephole optimization - try to merge it with all its

       def extensions and use extensions in the following

       order:

       - Try to merge only the def extensions, one by one.

       - Try to merge only the use extensions, one by one.

       - Try to merge any couple of use extensions simultaneously.

       - Try to merge any def extension with one or two uses

         extensions simultaneously.

    b. Handle each EXTENDED_DEF in it as if it was already merged with

       an extension.

  During the merge process we save the following data for each

  register in each basic block:

    a. The first instruction that defines the register in the basic

       block.

    b. The last instruction that defines the register in the basic

       block.

    c. The first extension of this register before the first

       instruction that defines it in the basic block.

    c. The first extension of this register after the last

       instruction that defines it in the basic block.

  This data will help us eliminate (or more precisely, not generate)

  locally redundant extensions, and will be useful in the next stage.

  While merging extensions with their reference there are 4 possible

  situations:

    a. A use extension was merged with the reference:

       Delete the extension instruction and save the merged reference

       for phase 4.  (For details, see see_use_extension_merged ())

    b. A use extension failed to be merged with the reference:

       If there is already such an extension in the same basic block

       and it is not dead at this point, delete the unmerged extension

       (it is locally redundant), otherwise properly update the above

       basic block data.

       (For details, see see_merge_one_use_extension ())

    c. A def extension was merged with the reference:

       Mark this extension as a merged_def extension and properly

       update the above basic block data.

       (For details, see see_merge_one_def_extension ())

    d. A def extension failed to be merged with the reference:

       Replace the definition of the NARROWmode register in the

       reference with the proper subreg of WIDEmode register and save

       the result as a merged reference.  Also, properly update the

       the above basic block data.

       (For details, see see_def_extension_not_merged ())

Phase 3: Eliminate globally redundant extensions.

In this phase, we set the bit vectors input of the edge based LCM

using the recorded data on the registers in each basic block.

We also save pointers for all the anticipatable and available

occurrences of the relevant extensions.  Then we run the LCM.

  a. Initialize the comp, antloc, kill bit vectors to zero and the

     transp bit vector to ones.

  b. Traverse over all the references.  Do this in basic block number

     and luid number forward order.  For each reference:

     - Go over all its use extensions.  For each such extension -

         If it is not dead from the beginning of the basic block SET

           the antloc bit of the current extension in the current

           basic block bits.

         If it is not dead till the end of the basic block SET the

           comp bit of the current extension in the current basic

           block bits.

     - Go over all its def extensions that were merged with

       it.  For each such extension -

         If it is not dead till the end of the basic block SET the

           comp bit of the current extension in the current basic

           block bits.

         RESET the proper transp and kill bits.

     - Go over all its def extensions that were not merged

       with it.  For each such extension -

         RESET the transp bit and SET the kill bit of the current

         extension in the current basic block bits.

  c. Run the edge based LCM.

Phase 4: Commit changes to the insn stream.

This is the only phase that actually changes the instruction stream.

Up to this point the optimization could be aborted at any time.

Here we insert extensions at their best placements and delete the

redundant ones according to the output of the LCM.  We also replace

some of the instructions according to the second phase merges results.

  a. Use the pre_delete_map (from the output of the LCM) in order to

     delete redundant extensions.  This will prevent them from been

     emitted in the first place.

  b. Insert extensions on edges where needed according to

     pre_insert_map and edge_list (from the output of the LCM).

  c. For each reference do-

     - Emit all the uses extensions that were not deleted until now,

       right before the reference.

     - Delete all the merged and unmerged def extensions from

       the instruction stream.

     - Replace the reference with the merged one, if exist.

The implementation consists of four data structures:

- Data structure I

  Purpose: To handle the relevancy of the uses, definitions and webs.

  Relevant structures: web_entry (from df.h), see_entry_extra_info.

  Details: This is a disjoint-set data structure.  Most of its functions are

           implemented in web.c.  Each definition and use in the code are

           elements.  A web_entry structure is allocated for each element to

           hold the element's relevancy and source_mode.  The union rules are

           defined in see_update_leader_extra_info ().

- Data structure II

  Purpose: To store references and their extensions (uses and defs)

           and to enable traverse over these references according to basic

           block order.

  Relevant structure: see_ref_s.

  Details: This data structure consists of an array of splay trees.  One splay

           tree for each basic block.  The splay tree nodes are references and

           the keys are the luids of the references.

           A see_ref_s structure is allocated for each reference.  It holds the

           reference itself, its def and uses extensions and later the merged

           version of the reference.

           Using this data structure we can traverse over all the references of

           a basic block and their extensions in forward order.

- Data structure III.

  Purpose: To store local properties of registers for each basic block.

           This data will later help us build the LCM sbitmap_vectors

           input.

  Relevant structure: see_register_properties.

  Details: This data structure consists of an array of hash tables.  One hash

           for each basic block.  The hash node are a register properties

           and the keys are the numbers of the registers.

           A see_register_properties structure is allocated for each register

           that we might be interested in its properties.

           Using this data structure we can easily find the properties of a

           register in a specific basic block.  This is necessary for locally

           redundancy elimination and for setting up the LCM input.

- Data structure IV.

  Purpose: To store the extensions that are candidate for PRE and their

           anticipatable and available occurrences.

  Relevant structure: see_occr, see_pre_extension_expr.

  Details: This data structure is a hash tables.  Its nodes are the extensions

           that are candidate for PRE.

           A see_pre_extension_expr structure is allocated for each candidate

           extension.  It holds a copy of the extension and a linked list of all

           the anticipatable and available occurrences of it.

           We use this data structure when we read the output of the LCM.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "obstack.h"

#include "rtl.h"

#include "output.h"

#include "df.h"

#include "insn-config.h"

#include "recog.h"

#include "expr.h"

#include "splay-tree.h"

#include "hashtab.h"

#include "regs.h"

#include "timevar.h"

#include "tree-pass.h"

/* Used to classify defs and uses according to relevancy.  */

enum entry_type {

  NOT_RELEVANT,

  SIGN_EXTENDED_DEF,

  ZERO_EXTENDED_DEF,

  EXTENDED_DEF,

  RELEVANT_USE

};

/* Used to classify extensions in relevant webs.  */

enum extension_type {

  DEF_EXTENSION,

  EXPLICIT_DEF_EXTENSION,

  IMPLICIT_DEF_EXTENSION,

  USE_EXTENSION

};

/* Global data structures and flags.  */

/* This structure will be assigned for each web_entry structure (defined

   in df.h).  It is placed in the extra_info field of a web_entry and holds the

   relevancy and source mode of the web_entry.  */

struct see_entry_extra_info

{

  /* The relevancy of the ref.  */

  enum entry_type relevancy;

  /* The relevancy of the ref.

     This field is updated only once - when this structure is created.  */

  enum entry_type local_relevancy;

  /* The source register mode.  */

  enum machine_mode source_mode;

  /* This field is used only if the relevancy is ZERO/SIGN_EXTENDED_DEF.

     It is updated only once when this structure is created.  */

  enum machine_mode local_source_mode;

  /* This field is used only if the relevancy is EXTENDED_DEF.

     It holds the narrowest mode that is sign extended.  */

  enum machine_mode source_mode_signed;

  /* This field is used only if the relevancy is EXTENDED_DEF.

     It holds the narrowest mode that is zero extended.  */

  enum machine_mode source_mode_unsigned;

};

/* There is one such structure for every reference.  It stores the reference

   itself as well as its extensions (uses and definitions).

   Used as the value in splay_tree see_bb_splay_ar[].  */

struct see_ref_s

{

  /* The luid of the insn.  */

  unsigned int luid;

  /* The insn of the ref.  */

  rtx insn;

  /* The merged insn that was formed from the reference's insn and extensions.

     If all merges failed, it remains NULL.  */

  rtx merged_insn;

  /* The def extensions of the reference that were not merged with

     it.  */

  htab_t unmerged_def_se_hash;

  /* The def extensions of the reference that were merged with

     it.  Implicit extensions of the reference will be stored here too.  */

  htab_t merged_def_se_hash;

  /* The uses extensions of reference.  */

  htab_t use_se_hash;

};

/* There is one such structure for every relevant extended register in a

   specific basic block.  This data will help us build the LCM sbitmap_vectors

   input.  */

struct see_register_properties

{

  /* The register number.  */

  unsigned int regno;

  /* The last luid of the reference that defines this register in this basic

     block.  */

  int last_def;

  /* The luid of the reference that has the first extension of this register

     that appears before any definition in this basic block.  */

  int first_se_before_any_def;

  /* The luid of the reference that has the first extension of this register

     that appears after the last definition in this basic block.  */

  int first_se_after_last_def;

};

/* Occurrence of an expression.

   There must be at most one available occurrence and at most one anticipatable

   occurrence per basic block.  */

struct see_occr

{

  /* Next occurrence of this expression.  */

  struct see_occr *next;

  /* The insn that computes the expression.  */

  rtx insn;

  int block_num;

};

/* There is one such structure for every relevant extension expression.

   It holds a copy of this extension instruction as well as a linked lists of

   pointers to all the antic and avail occurrences of it.  */

struct see_pre_extension_expr

{

  /* A copy of the extension instruction.  */

  rtx se_insn;

  /* Index in the available expression bitmaps.  */

  int bitmap_index;

  /* List of anticipatable occurrences in basic blocks in the function.

     An "anticipatable occurrence" is the first occurrence in the basic block,

     the operands are not modified in the basic block prior to the occurrence

     and the output is not used between the start of the block and the

     occurrence.  */

  struct see_occr *antic_occr;

  /* List of available occurrence in basic blocks in the function.

     An "available occurrence" is the last occurrence in the basic block and

     the operands are not modified by following statements in the basic block

     [including this insn].  */

  struct see_occr *avail_occr;

};

/* Helper structure for the note_uses and see_replace_src functions.  */

struct see_replace_data

{

  rtx from;

  rtx to;

};

/* Helper structure for the note_uses and see_mentioned_reg functions.  */

struct see_mentioned_reg_data

{

  rtx reg;

  bool mentioned;

};

/* A data flow object that will be created once and used throughout the

   optimization.  */

static struct df *df = NULL;

/* An array of web_entries.  The i'th definition in the df object is associated

   with def_entry[i]  */

static struct web_entry *def_entry = NULL;

/* An array of web_entries.  The i'th use in the df object is associated with

   use_entry[i]  */

static struct web_entry *use_entry = NULL;

/* Array of splay_trees.

   see_bb_splay_ar[i] refers to the splay tree of the i'th basic block.

   The splay tree will hold see_ref_s structures.  The key is the luid

   of the insn.  This way we can traverse over the references of each basic

   block in forward or backward order.  */

static splay_tree *see_bb_splay_ar = NULL;

/* Array of hashes.

   see_bb_hash_ar[i] refers to the hash of the i'th basic block.

   The hash will hold see_register_properties structure.  The key is regno.  */

static htab_t *see_bb_hash_ar = NULL;

/* Hash table that holds a copy of all the extensions.  The key is the right

   hand side of the se_insn field.  */

static htab_t see_pre_extension_hash = NULL;

/* Local LCM properties of expressions.  */

/* Nonzero for expressions that are transparent in the block.  */

static sbitmap *transp = NULL;

/* Nonzero for expressions that are computed (available) in the block.  */

static sbitmap *comp = NULL;

/* Nonzero for expressions that are locally anticipatable in the block.  */

static sbitmap *antloc = NULL;

/* Nonzero for expressions that are locally killed in the block.  */

static sbitmap *ae_kill = NULL;

/* Nonzero for expressions which should be inserted on a specific edge.  */

static sbitmap *pre_insert_map = NULL;

/* Nonzero for expressions which should be deleted in a specific block.  */

static sbitmap *pre_delete_map = NULL;

/* Contains the edge_list returned by pre_edge_lcm.  */

static struct edge_list *edge_list = NULL;

/* Records the last basic block at the beginning of the optimization.  */

static int last_bb;

/* Records the number of uses at the beginning of the optimization.  */

static unsigned int uses_num;

/* Records the number of definitions at the beginning of the optimization.  */

static unsigned int defs_num;

#define ENTRY_EI(ENTRY) ((struct see_entry_extra_info *) (ENTRY)->extra_info)

/* Functions implementation.  */

/*  Verifies that EXTENSION's pattern is this:

    set (reg/subreg reg1) (sign/zero_extend:WIDEmode (reg/subreg reg2))

    If it doesn't have the expected pattern return NULL.

    Otherwise, if RETURN_DEST_REG is set, return reg1 else return reg2.  */

static rtx

see_get_extension_reg (rtx extension, bool return_dest_reg)

{

  rtx set, rhs, lhs;

  rtx reg1 = NULL;

  rtx reg2 = NULL;

  /* Parallel pattern for extension not supported for the moment.  */

  if (GET_CODE (PATTERN (extension)) == PARALLEL)

    return NULL;

  set = single_set (extension);

  if (!set)

    return NULL;

  lhs = SET_DEST (set);

  rhs = SET_SRC (set);

  if (REG_P (lhs))

    reg1 = lhs;

  else if (REG_P (SUBREG_REG (lhs)))

    reg1 = SUBREG_REG (lhs);

  else

    return NULL;

  if (GET_CODE (rhs) != SIGN_EXTEND && GET_CODE (rhs) != ZERO_EXTEND)

    return NULL;

  rhs = XEXP (rhs, 0);

  if (REG_P (rhs))

    reg2 = rhs;

  else if (REG_P (SUBREG_REG (rhs)))

    reg2 = SUBREG_REG (rhs);

  else

    return NULL;

  if (return_dest_reg)

    return reg1;

  return reg2;

}

/*  Verifies that EXTENSION's pattern is this:

    set (reg/subreg reg1) (sign/zero_extend: (...expr...)

    If it doesn't have the expected pattern return UNKNOWN.

    Otherwise, set SOURCE_MODE to be the mode of the extended expr and return

    the rtx code of the extension.  */

static enum rtx_code

see_get_extension_data (rtx extension, enum machine_mode *source_mode)

{

  rtx rhs, lhs, set;

  if (!extension || !INSN_P (extension))

    return UNKNOWN;

  /* Parallel pattern for extension not supported for the moment.  */

  if (GET_CODE (PATTERN (extension)) == PARALLEL)

    return NOT_RELEVANT;

  set = single_set (extension);

  if (!set)

    return NOT_RELEVANT;

  rhs = SET_SRC (set);

  lhs = SET_DEST (set);

  /* Don't handle extensions to something other then register or

     subregister.  */

  if (!REG_P (lhs) && !SUBREG_REG (lhs))

    return UNKNOWN;

  if (GET_CODE (rhs) != SIGN_EXTEND && GET_CODE (rhs) != ZERO_EXTEND)

    return UNKNOWN;

  if (!REG_P (XEXP (rhs, 0))

      && !(GET_CODE (XEXP (rhs, 0)) == SUBREG

           && REG_P (SUBREG_REG (XEXP (rhs, 0)))))

    return UNKNOWN;

  *source_mode = GET_MODE (XEXP (rhs, 0));

  if (GET_CODE (rhs) == SIGN_EXTEND)

    return SIGN_EXTEND;

  return ZERO_EXTEND;

}

/* Generate instruction with the pattern:

   set ((reg r) (sign/zero_extend (subreg:mode (reg r))))

   (the register r on both sides of the set is the same register).

   And recognize it.

   If the recognition failed, this is very bad, return NULL (This will abort

   the entire optimization).

   Otherwise, return the generated instruction.  */

static rtx

see_gen_normalized_extension (rtx reg, enum rtx_code extension_code,

                              enum machine_mode mode)

{

  rtx subreg, insn;

  rtx extension = NULL;

  if (!reg

      || !REG_P (reg)

      || (extension_code != SIGN_EXTEND && extension_code != ZERO_EXTEND))

    return NULL;

  subreg = gen_lowpart_SUBREG (mode, reg);

  if (extension_code == SIGN_EXTEND)

    extension = gen_rtx_SIGN_EXTEND (GET_MODE (reg), subreg);

  else

    extension = gen_rtx_ZERO_EXTEND (GET_MODE (reg), subreg);

  start_sequence ();

  emit_insn (gen_rtx_SET (VOIDmode, reg, extension));

  insn = get_insns ();

  end_sequence ();

  if (insn_invalid_p (insn))

    /* Recognition failed, this is very bad for this optimization.

       Abort the optimization.  */

    return NULL;

  return insn;

}

/* Hashes and splay_trees related functions implementation.  */

/* Helper functions for the pre_extension hash.

   This kind of hash will hold see_pre_extension_expr structures.

   The key is the right hand side of the se_insn field.

   Note that the se_insn is an expression that looks like:

   set ((reg:WIDEmode r1) (sign_extend:WIDEmode

                           (subreg:NARROWmode (reg:WIDEmode r2))))  */

/* Return TRUE if P1 has the same value in its rhs as P2.

   Otherwise, return FALSE.

   P1 and P2 are see_pre_extension_expr structures.  */

static int

eq_descriptor_pre_extension (const void *p1, const void *p2)

{

  const struct see_pre_extension_expr *extension1 = p1;

  const struct see_pre_extension_expr *extension2 = p2;

  rtx set1 = single_set (extension1->se_insn);

  rtx set2 = single_set (extension2->se_insn);

  rtx rhs1, rhs2;

  gcc_assert (set1 && set2);

  rhs1 = SET_SRC (set1);

  rhs2 = SET_SRC (set2);

  return rtx_equal_p (rhs1, rhs2);

}

/* P is a see_pre_extension_expr struct, use the RHS of the se_insn field.

   Note that the RHS is an expression that looks like this:

   (sign_extend:WIDEmode (subreg:NARROWmode (reg:WIDEmode r)))  */

static hashval_t

hash_descriptor_pre_extension (const void *p)

{

  const struct see_pre_extension_expr *extension = p;

  rtx set = single_set (extension->se_insn);

  rtx rhs;

  gcc_assert (set);

  rhs = SET_SRC (set);

  return hash_rtx (rhs, GET_MODE (rhs), 0, NULL, 0);

}

/* Free the allocated memory of the current see_pre_extension_expr struct.