2008-05-20 Kai Tietz <kai.tietz@onevision.com>

[official-gcc.git] / gcc / see.c

/* Sign extension elimination optimization for GNU compiler.
   Copyright (C) 2005, 2006, 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"
#include "dce.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;
};

/* 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)
\f
/* 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.
   
   It frees the two linked list of the occurrences structures.  */

static void
hash_del_pre_extension (void *p)
{
  struct see_pre_extension_expr *extension = p;
  struct see_occr *curr_occr = extension->antic_occr;
  struct see_occr *next_occr = NULL;

  /*  Free the linked list of the anticipatable occurrences.  */
  while (curr_occr)
    {
      next_occr = curr_occr->next;
      free (curr_occr);
      curr_occr = next_occr;
    }

  /*  Free the linked list of the available occurrences.  */
  curr_occr = extension->avail_occr;
  while (curr_occr)
    {
      next_occr = curr_occr->next;
      free (curr_occr);
      curr_occr = next_occr;
    }

  /* Free the see_pre_extension_expr structure itself.  */
  free (extension);
}


/* Helper functions for the register_properties hash.
   This kind of hash will hold see_register_properties structures.

   The value of the key is the regno field of the structure.  */

/* Return TRUE if P1 has the same value in the regno field as P2.
   Otherwise, return FALSE.
   Where P1 and P2 are see_register_properties structures.  */

static int
eq_descriptor_properties (const void *p1, const void *p2)
{
  const struct see_register_properties *curr_prop1 = p1;
  const struct see_register_properties *curr_prop2 = p2;

  return curr_prop1->regno == curr_prop2->regno;
}


/* P is a see_register_properties struct, use the register number in the
   regno field.  */

static hashval_t
hash_descriptor_properties (const void *p)
{
  const struct see_register_properties *curr_prop = p;
  return curr_prop->regno;
}


/* Free the allocated memory of the current see_register_properties struct.  */
static void
hash_del_properties (void *p)
{
  struct see_register_properties *curr_prop = p;
  free (curr_prop);
}


/* Helper functions for an extension hash.
   This kind of hash will hold insns that look like:

   set ((reg:WIDEmode r1) (sign_extend:WIDEmode
                           (subreg:NARROWmode (reg:WIDEmode r2))))
   or
   set ((reg:WIDEmode r1) (sign_extend:WIDEmode (reg:NARROWmode r2)))

   The value of the key is (REGNO (reg:WIDEmode r1))
   It is possible to search this hash in two ways:
   1.  By a register rtx. The Value that is been compared to the keys is the
       REGNO of it.
   2.  By an insn with the above pattern. The Value that is been compared to
       the keys is the REGNO of the reg on the lhs.  */

/* Return TRUE if P1 has the same value as P2.  Otherwise, return FALSE.
   Where P1 is an insn and P2 is an insn or a register.  */

static int
eq_descriptor_extension (const void *p1, const void *p2)
{
  const_rtx const insn = (const_rtx) p1;
  const_rtx const element = (const_rtx) p2;
  rtx set1 = single_set (insn);
  rtx dest_reg1;
  rtx set2 = NULL;
  const_rtx dest_reg2 = NULL;

  gcc_assert (set1 && element && (REG_P (element) || INSN_P (element)));

  dest_reg1 = SET_DEST (set1);

  if (INSN_P (element))
    {
      set2 = single_set (element);
      dest_reg2 = SET_DEST (set2);
    }
  else
    dest_reg2 = element;

  return REGNO (dest_reg1) == REGNO (dest_reg2);
}


/* If P is an insn, use the register number of its lhs
   otherwise, P is a register, use its number.  */

static hashval_t
hash_descriptor_extension (const void *p)
{
  const_rtx const r = (const_rtx) p;
  rtx set, lhs;

  if (r && REG_P (r))
    return REGNO (r);

  gcc_assert (r && INSN_P (r));
  set = single_set (r);
  gcc_assert (set);
  lhs = SET_DEST (set);
  return REGNO (lhs);
}


/* Helper function for a see_bb_splay_ar[i] splay tree.
   It frees all the allocated memory of a struct see_ref_s pointer.

   VALUE is the value of a splay tree node.  */

static void
see_free_ref_s (splay_tree_value value)
{
  struct see_ref_s *ref_s = (struct see_ref_s *)value;

  if (ref_s->unmerged_def_se_hash)
    htab_delete (ref_s->unmerged_def_se_hash);
  if (ref_s->merged_def_se_hash)
    htab_delete (ref_s->merged_def_se_hash);
  if (ref_s->use_se_hash)
    htab_delete (ref_s->use_se_hash);
  free (ref_s);
}


/* Rest of the implementation.  */

/* Search the extension hash for a suitable entry for EXTENSION.
   TYPE is the type of EXTENSION (USE_EXTENSION or DEF_EXTENSION).

   If TYPE is DEF_EXTENSION we need to normalize EXTENSION before searching the
   extension hash.

   If a suitable entry was found, return the slot.  Otherwise, store EXTENSION
   in the hash and return NULL.  */

static struct see_pre_extension_expr *
see_seek_pre_extension_expr (rtx extension, enum extension_type type)
{
  struct see_pre_extension_expr **slot_pre_exp, temp_pre_exp;
  rtx dest_extension_reg = see_get_extension_reg (extension, 1);
  enum rtx_code extension_code;
  enum machine_mode source_extension_mode;

  if (type == DEF_EXTENSION)
    {
      extension_code = see_get_extension_data (extension,
                                               &source_extension_mode);
      gcc_assert (extension_code != UNKNOWN);
      extension =
        see_gen_normalized_extension (dest_extension_reg, extension_code,
                                      source_extension_mode);
    }
  temp_pre_exp.se_insn = extension;
  slot_pre_exp =
    (struct see_pre_extension_expr **) htab_find_slot (see_pre_extension_hash,
                                                        &temp_pre_exp, INSERT);
  if (*slot_pre_exp == NULL)
    /* This is the first time this extension instruction is encountered.  Store
       it in the hash.  */
    {
      (*slot_pre_exp) = xmalloc (sizeof (struct see_pre_extension_expr));
      (*slot_pre_exp)->se_insn = extension;
      (*slot_pre_exp)->bitmap_index =
        (htab_elements (see_pre_extension_hash) - 1);
      (*slot_pre_exp)->antic_occr = NULL;
      (*slot_pre_exp)->avail_occr = NULL;
      return NULL;
    }
  return *slot_pre_exp;
}


/* This function defines how to update the extra_info of the web_entry.

   FIRST is the pointer of the extra_info of the first web_entry.
   SECOND is the pointer of the extra_info of the second web_entry.
   The first web_entry will be the predecessor (leader) of the second web_entry
   after the union.
   
   Return true if FIRST and SECOND points to the same web entry structure and 
   nothing is done.  Otherwise, return false.  */

static bool
see_update_leader_extra_info (struct web_entry *first, struct web_entry *second)
{
  struct see_entry_extra_info *first_ei, *second_ei;

  first = unionfind_root (first);
  second = unionfind_root (second);

  if (unionfind_union (first, second))
    return true;

  first_ei = (struct see_entry_extra_info *) first->extra_info;
  second_ei = (struct see_entry_extra_info *) second->extra_info;

  gcc_assert (first_ei && second_ei);

  if (second_ei->relevancy == NOT_RELEVANT)
    {
      first_ei->relevancy = NOT_RELEVANT;
      return false;
    }
  switch (first_ei->relevancy)
    {
    case NOT_RELEVANT:
      break;
    case RELEVANT_USE:
      switch (second_ei->relevancy)
        {
        case RELEVANT_USE:
          break;
        case EXTENDED_DEF:
          first_ei->relevancy = second_ei->relevancy;
          first_ei->source_mode_signed = second_ei->source_mode_signed;
          first_ei->source_mode_unsigned = second_ei->source_mode_unsigned;
          break;
        case SIGN_EXTENDED_DEF:
        case ZERO_EXTENDED_DEF:
          first_ei->relevancy = second_ei->relevancy;
          first_ei->source_mode = second_ei->source_mode;
          break;
        default:
          gcc_unreachable ();
        }
      break;
    case SIGN_EXTENDED_DEF:
      switch (second_ei->relevancy)
        {
        case SIGN_EXTENDED_DEF:
          /* The mode of the root should be the wider one in this case.  */
          first_ei->source_mode =
            (first_ei->source_mode > second_ei->source_mode) ?
            first_ei->source_mode : second_ei->source_mode;
          break;
        case RELEVANT_USE:
          break;
        case ZERO_EXTENDED_DEF:
          /* Don't mix webs with zero extend and sign extend.  */
          first_ei->relevancy = NOT_RELEVANT;
          break;
        case EXTENDED_DEF:
          if (second_ei->source_mode_signed == MAX_MACHINE_MODE)
            first_ei->relevancy = NOT_RELEVANT;
          else
            /* The mode of the root should be the wider one in this case.  */
            first_ei->source_mode =
              (first_ei->source_mode > second_ei->source_mode_signed) ?
              first_ei->source_mode : second_ei->source_mode_signed;
          break;
        default:
          gcc_unreachable ();
        }
      break;
    /* This case is similar to the previous one, with little changes.  */
    case ZERO_EXTENDED_DEF:
      switch (second_ei->relevancy)
        {
        case SIGN_EXTENDED_DEF:
          /* Don't mix webs with zero extend and sign extend.  */
          first_ei->relevancy = NOT_RELEVANT;
          break;
        case RELEVANT_USE:
          break;
        case ZERO_EXTENDED_DEF:
          /* The mode of the root should be the wider one in this case.  */
          first_ei->source_mode =
            (first_ei->source_mode > second_ei->source_mode) ?
            first_ei->source_mode : second_ei->source_mode;
          break;
        case EXTENDED_DEF:
          if (second_ei->source_mode_unsigned == MAX_MACHINE_MODE)
            first_ei->relevancy = NOT_RELEVANT;
          else
            /* The mode of the root should be the wider one in this case.  */
            first_ei->source_mode =
              (first_ei->source_mode > second_ei->source_mode_unsigned) ?
              first_ei->source_mode : second_ei->source_mode_unsigned;
          break;
        default:
          gcc_unreachable ();
        }
      break;
    case EXTENDED_DEF:
      if (first_ei->source_mode_signed != MAX_MACHINE_MODE
          && first_ei->source_mode_unsigned != MAX_MACHINE_MODE)
        {
          switch (second_ei->relevancy)
            {
            case SIGN_EXTENDED_DEF:
              first_ei->relevancy = SIGN_EXTENDED_DEF;
              first_ei->source_mode =
                (first_ei->source_mode_signed > second_ei->source_mode) ?
                first_ei->source_mode_signed : second_ei->source_mode;
              break;
            case RELEVANT_USE:
              break;
            case ZERO_EXTENDED_DEF:
              first_ei->relevancy = ZERO_EXTENDED_DEF;
              first_ei->source_mode =
                (first_ei->source_mode_unsigned > second_ei->source_mode) ?
                first_ei->source_mode_unsigned : second_ei->source_mode;
              break;
            case EXTENDED_DEF:
              if (second_ei->source_mode_unsigned != MAX_MACHINE_MODE)
                first_ei->source_mode_unsigned =
                  (first_ei->source_mode_unsigned >
                  second_ei->source_mode_unsigned) ?
                  first_ei->source_mode_unsigned :
                  second_ei->source_mode_unsigned;
              if (second_ei->source_mode_signed != MAX_MACHINE_MODE)
                first_ei->source_mode_signed =
                  (first_ei->source_mode_signed >
                  second_ei->source_mode_signed) ?
                  first_ei->source_mode_signed : second_ei->source_mode_signed;
              break;
            default:
              gcc_unreachable ();
            }
        }
      else if (first_ei->source_mode_signed == MAX_MACHINE_MODE)
        {
          gcc_assert (first_ei->source_mode_unsigned != MAX_MACHINE_MODE);
          switch (second_ei->relevancy)
            {
            case SIGN_EXTENDED_DEF:
              first_ei->relevancy = NOT_RELEVANT;
              break;
            case RELEVANT_USE:
              break;
            case ZERO_EXTENDED_DEF:
              first_ei->relevancy = ZERO_EXTENDED_DEF;
              first_ei->source_mode =
                (first_ei->source_mode_unsigned > second_ei->source_mode) ?
                first_ei->source_mode_unsigned : second_ei->source_mode;
              break;
            case EXTENDED_DEF:
              if (second_ei->source_mode_unsigned == MAX_MACHINE_MODE)
                first_ei->relevancy = NOT_RELEVANT;
              else
                first_ei->source_mode_unsigned =
                  (first_ei->source_mode_unsigned >
                  second_ei->source_mode_unsigned) ?
                  first_ei->source_mode_unsigned :
                  second_ei->source_mode_unsigned;
              break;
            default:
              gcc_unreachable ();
            }
        }
      else
        {
          gcc_assert (first_ei->source_mode_unsigned == MAX_MACHINE_MODE);
          gcc_assert (first_ei->source_mode_signed != MAX_MACHINE_MODE);
          switch (second_ei->relevancy)
            {
            case SIGN_EXTENDED_DEF:
              first_ei->relevancy = SIGN_EXTENDED_DEF;
              first_ei->source_mode =
                (first_ei->source_mode_signed > second_ei->source_mode) ?
                first_ei->source_mode_signed : second_ei->source_mode;
              break;
            case RELEVANT_USE:
              break;
            case ZERO_EXTENDED_DEF:
              first_ei->relevancy = NOT_RELEVANT;
              break;
            case EXTENDED_DEF:
              if (second_ei->source_mode_signed == MAX_MACHINE_MODE)
                first_ei->relevancy = NOT_RELEVANT;
              else
                first_ei->source_mode_signed =
                  (first_ei->source_mode_signed >
                  second_ei->source_mode_signed) ?
                  first_ei->source_mode_signed : second_ei->source_mode_signed;
              break;
            default:
              gcc_unreachable ();
            }
        }
      break;
    default:
      /* Unknown patern type.  */
      gcc_unreachable ();
    }

  return false;
}


/* Free global data structures.  */

static void
see_free_data_structures (void)
{
  int i;
  unsigned int j;

  /* Free the bitmap vectors.  */
  if (transp)
    {
      sbitmap_vector_free (transp);
      transp = NULL;
      sbitmap_vector_free (comp);
      comp = NULL;
      sbitmap_vector_free (antloc);
      antloc = NULL;
      sbitmap_vector_free (ae_kill);
      ae_kill = NULL;
    }
  if (pre_insert_map)
    {
      sbitmap_vector_free (pre_insert_map);
      pre_insert_map = NULL;
    }
  if (pre_delete_map)
    {
      sbitmap_vector_free (pre_delete_map);
      pre_delete_map = NULL;
    }
  if (edge_list)
    {
      free_edge_list (edge_list);
      edge_list = NULL;
    }

  /*  Free the extension hash.  */
  htab_delete (see_pre_extension_hash);

  /*  Free the array of hashes.  */
  for (i = 0; i < last_bb; i++)
    if (see_bb_hash_ar[i])
      htab_delete (see_bb_hash_ar[i]);
  free (see_bb_hash_ar);

  /*  Free the array of splay trees.  */
  for (i = 0; i < last_bb; i++)
    if (see_bb_splay_ar[i])
      splay_tree_delete (see_bb_splay_ar[i]);
  free (see_bb_splay_ar);

  /*  Free the array of web entries and their extra info field.  */
  for (j = 0; j < defs_num; j++)
    free (def_entry[j].extra_info);
  free (def_entry);
  for (j = 0; j < uses_num; j++)
    free (use_entry[j].extra_info);
  free (use_entry);
}


/* Initialize global data structures and variables.  */

static void
see_initialize_data_structures (void)
{
  unsigned int max_reg = max_reg_num ();
  unsigned int i;

  /* Build the df object. */
  df_set_flags (DF_EQ_NOTES);
  df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
  df_analyze ();
  df_set_flags (DF_DEFER_INSN_RESCAN);

  if (dump_file)
    df_dump (dump_file);

  /* Record the last basic block at the beginning of the optimization.  */
  last_bb = last_basic_block;

  /* Record the number of uses and defs at the beginning of the optimization.  */
  uses_num = 0;
  defs_num = 0;
  for (i = 0; i < max_reg; i++) 
    {
      uses_num += DF_REG_USE_COUNT (i) + DF_REG_EQ_USE_COUNT (i);
      defs_num += DF_REG_DEF_COUNT (i);
    }

  /*  Allocate web entries array for the union-find data structure.  */
  def_entry = xcalloc (defs_num, sizeof (struct web_entry));
  use_entry = xcalloc (uses_num, sizeof (struct web_entry));

  /*  Allocate an array of splay trees.
      One splay tree for each basic block.  */
  see_bb_splay_ar = xcalloc (last_bb, sizeof (splay_tree));

  /*  Allocate an array of hashes.
      One hash for each basic block.  */
  see_bb_hash_ar = xcalloc (last_bb, sizeof (htab_t));

  /*  Allocate the extension hash.  It will hold the extensions that we want
      to PRE.  */
  see_pre_extension_hash = htab_create (10, 
                                        hash_descriptor_pre_extension, 
                                        eq_descriptor_pre_extension,
                                        hash_del_pre_extension);
}


/* Function called by note_uses to check if a register is used in a
   subexpressions.

   X is a pointer to the subexpression and DATA is a pointer to a
   see_mentioned_reg_data structure that contains the register to look for and
   a place for the result.  */

static void
see_mentioned_reg (rtx *x, void *data)
{
  struct see_mentioned_reg_data *d
    = (struct see_mentioned_reg_data *) data;

  if (reg_mentioned_p (d->reg, *x))
    d->mentioned = true;
}


/* We don't want to merge a use extension with a reference if the extended
   register is used only in a simple move instruction.  We also don't want to
   merge a def extension with a reference if the source register of the
   extension is defined only in a simple move in the reference.

   REF is the reference instruction.
   EXTENSION is the use extension or def extension instruction.
   TYPE is the type of the extension (use or def).

   Return true if the reference is complicated enough, so we would like to merge
   it with the extension.  Otherwise, return false.  */

static bool
see_want_to_be_merged_with_extension (rtx ref, rtx extension,
                                      enum extension_type type)
{
  rtx pat;
  rtx dest_extension_reg = see_get_extension_reg (extension, 1);
  rtx source_extension_reg = see_get_extension_reg (extension, 0);
  enum rtx_code code;
  struct see_mentioned_reg_data d;
  int i;

  pat = PATTERN (ref);
  code = GET_CODE (pat);

  if (code == PARALLEL)
    {
      for (i = 0; i < XVECLEN (pat, 0); i++)
        {
          rtx sub = XVECEXP (pat, 0, i);

          if (GET_CODE (sub) == SET
              && (REG_P (SET_DEST (sub))
                  || (GET_CODE (SET_DEST (sub)) == SUBREG
                      && REG_P (SUBREG_REG (SET_DEST (sub)))))
              && (REG_P (SET_SRC (sub))
                  || (GET_CODE (SET_SRC (sub)) == SUBREG
                      && REG_P (SUBREG_REG (SET_SRC (sub))))))
            {
              /* This is a simple move SET.  */
              if (type == DEF_EXTENSION
                  && reg_mentioned_p (source_extension_reg, SET_DEST (sub)))
                return false;
            }
          else
            {
              /* This is not a simple move SET.
                 Check if it uses the source of the extension.  */
              if (type == USE_EXTENSION)
                {
                  d.reg = dest_extension_reg;
                  d.mentioned = false;
                  note_uses (&sub, see_mentioned_reg, &d);
                  if (d.mentioned)
                    return true;
                }
            }
        }
      if (type == USE_EXTENSION)
        return false;
    }
  else
    {
      if (code == SET
          && (REG_P (SET_DEST (pat))
              || (GET_CODE (SET_DEST (pat)) == SUBREG
                  && REG_P (SUBREG_REG (SET_DEST (pat)))))
          && (REG_P (SET_SRC (pat))
              || (GET_CODE (SET_SRC (pat)) == SUBREG
                  && REG_P (SUBREG_REG (SET_SRC (pat))))))
        /* This is a simple move SET.  */
        return false;
     }

  return true;
}


/* Print the register number of the current see_register_properties
   structure.

   This is a subroutine of see_main called via htab_traverse.
   SLOT contains the current see_register_properties structure pointer.  */

static int
see_print_register_properties (void **slot, void *b ATTRIBUTE_UNUSED)
{
  struct see_register_properties *prop = *slot;

  gcc_assert (prop);
  fprintf (dump_file, "Property found for register %d\n", prop->regno);
  return 1;
}


/* Print the extension instruction of the current see_register_properties
   structure.

   This is a subroutine of see_main called via htab_traverse.
   SLOT contains the current see_pre_extension_expr structure pointer.  */

static int
see_print_pre_extension_expr (void **slot, void *b ATTRIBUTE_UNUSED)
{
  struct see_pre_extension_expr *pre_extension = *slot;

  gcc_assert (pre_extension
              && pre_extension->se_insn
              && INSN_P (pre_extension->se_insn));

  fprintf (dump_file, "Index %d for:\n", pre_extension->bitmap_index);
  print_rtl_single (dump_file, pre_extension->se_insn);

  return 1;
}


/* Phase 4 implementation: Commit changes to the insn stream.  */

/* Delete the merged def extension.

   This is a subroutine of see_commit_ref_changes called via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_delete_merged_def_extension (void **slot, void *b ATTRIBUTE_UNUSED)
{
  rtx def_se = *slot;

  if (dump_file)
    {
      fprintf (dump_file, "Deleting merged def extension:\n");
      print_rtl_single (dump_file, def_se);
    }

  if (INSN_DELETED_P (def_se))
    /* This def extension is an implicit one.  No need to delete it since
       it is not in the insn stream.  */
    return 1;

  delete_insn (def_se);
  return 1;
}


/* Delete the unmerged def extension.

   This is a subroutine of see_commit_ref_changes called via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_delete_unmerged_def_extension (void **slot, void *b ATTRIBUTE_UNUSED)
{
  rtx def_se = *slot;

  if (dump_file)
    {
      fprintf (dump_file, "Deleting unmerged def extension:\n");
      print_rtl_single (dump_file, def_se);
    }

  delete_insn (def_se);
  return 1;
}


/* Emit the non-redundant use extension to the instruction stream.

   This is a subroutine of see_commit_ref_changes called via htab_traverse.

   SLOT contains the current use extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_emit_use_extension (void **slot, void *b)
{
  rtx use_se = *slot;
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;

  if (INSN_DELETED_P (use_se))
    /* This use extension was previously removed according to the lcm
       output.  */
    return 1;

  if (dump_file)
    {
      fprintf (dump_file, "Inserting use extension:\n");
      print_rtl_single (dump_file, use_se);
    }

  add_insn_before (use_se, curr_ref_s->insn, NULL);

  return 1;
}


/* For each relevant reference:
   a. Emit the non-redundant use extensions.
   b. Delete the def extensions.
   c. Replace the original reference with the merged one (if exists) and add the
      move instructions that were generated.

   This is a subroutine of see_commit_changes called via splay_tree_foreach.

   STN is the current node in the see_bb_splay_ar[i] splay tree.  It holds a
   see_ref_s structure.  */

static int
see_commit_ref_changes (splay_tree_node stn,
                        void *data ATTRIBUTE_UNUSED)
{
  htab_t use_se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
  htab_t unmerged_def_se_hash =
    ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
  htab_t merged_def_se_hash =
    ((struct see_ref_s *) (stn->value))->merged_def_se_hash;
  rtx ref = ((struct see_ref_s *) (stn->value))->insn;
  rtx merged_ref = ((struct see_ref_s *) (stn->value))->merged_insn;

  /* Emit the non-redundant use extensions.  */
  if (use_se_hash)
    htab_traverse_noresize (use_se_hash, see_emit_use_extension,
                            (PTR) (stn->value));

  /* Delete the def extensions.  */
  if (unmerged_def_se_hash)
    htab_traverse (unmerged_def_se_hash, see_delete_unmerged_def_extension,
                   (PTR) (stn->value));

  if (merged_def_se_hash)
    htab_traverse (merged_def_se_hash, see_delete_merged_def_extension,
                   (PTR) (stn->value));

  /* Replace the original reference with the merged one (if exists) and add the
     move instructions that were generated.  */
  if (merged_ref && !INSN_DELETED_P (ref))
    {
      if (dump_file)
        {
          fprintf (dump_file, "Replacing orig reference:\n");
          print_rtl_single (dump_file, ref);
          fprintf (dump_file, "With merged reference:\n");
          print_rtl_single (dump_file, merged_ref);
        }
      emit_insn_after (merged_ref, ref);
      delete_insn (ref);
    }

  /* Continue to the next reference.  */
  return 0;
}


/* Insert partially redundant expressions on edges to make the expressions fully
   redundant.

   INDEX_MAP is a mapping of an index to an expression.
   Return true if an instruction was inserted on an edge.
   Otherwise, return false.  */

static bool
see_pre_insert_extensions (struct see_pre_extension_expr **index_map)
{
  int num_edges = NUM_EDGES (edge_list);
  int set_size = pre_insert_map[0]->size;
  size_t pre_extension_num = htab_elements (see_pre_extension_hash);

  int did_insert = 0;
  int e;
  int i;
  int j;

  for (e = 0; e < num_edges; e++)
    {
      int indx;
      basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);

      for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
        {
          SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];

          for (j = indx; insert && j < (int) pre_extension_num;
               j++, insert >>= 1)
            if (insert & 1)
              {
                struct see_pre_extension_expr *expr = index_map[j];
                int idx = expr->bitmap_index;
                rtx se_insn = NULL;
                edge eg = INDEX_EDGE (edge_list, e);

                start_sequence ();
                emit_insn (PATTERN (expr->se_insn));
                se_insn = get_insns ();
                end_sequence ();

                if (eg->flags & EDGE_ABNORMAL)
                  {
                    rtx new_insn = NULL;

                    new_insn = insert_insn_end_bb_new (se_insn, bb);
                    gcc_assert (new_insn && INSN_P (new_insn));

                    if (dump_file)
                      {
                        fprintf (dump_file,
                                 "PRE: end of bb %d, insn %d, ",
                                 bb->index, INSN_UID (new_insn));
                        fprintf (dump_file,
                                 "inserting expression %d\n", idx);
                      }
                  }
                else
                  {
                    insert_insn_on_edge (se_insn, eg);

                    if (dump_file)
                      {
                        fprintf (dump_file, "PRE: edge (%d,%d), ",
                                 bb->index,
                                 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
                        fprintf (dump_file, "inserting expression %d\n", idx);
                      }
                  }
                did_insert = true;
              }
        }
    }
  return did_insert;
}


/* Since all the redundant extensions must be anticipatable, they must be a use
   extensions.  Mark them as deleted.  This will prevent them from been emitted
   in the first place.

   This is a subroutine of see_commit_changes called via htab_traverse.

   SLOT contains the current see_pre_extension_expr structure pointer.  */

static int
see_pre_delete_extension (void **slot, void *b ATTRIBUTE_UNUSED)
{
  struct see_pre_extension_expr *expr = *slot;
  struct see_occr *occr;
  int indx = expr->bitmap_index;

  for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
    {
      if (TEST_BIT (pre_delete_map[occr->block_num], indx))
        {
          /* Mark as deleted.  */
          INSN_DELETED_P (occr->insn) = 1;
          if (dump_file)
            {
              fprintf (dump_file,"Redundant extension deleted:\n");
              print_rtl_single (dump_file, occr->insn);
            }
        }
    }
  return 1;
}


/* Create the index_map mapping of an index to an expression.

   This is a subroutine of see_commit_changes called via htab_traverse.

   SLOT contains the current see_pre_extension_expr structure pointer.
   B a pointer to see_pre_extension_expr structure pointer.  */

static int
see_map_extension (void **slot, void *b)
{
  struct see_pre_extension_expr *expr = *slot;
  struct see_pre_extension_expr **index_map =
    (struct see_pre_extension_expr **) b;

  index_map[expr->bitmap_index] = expr;

  return 1;
}


/* Phase 4 top level function.
   In this phase we finally change the instruction stream.
   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 phase 2 merges results.  */

static void
see_commit_changes (void)
{
  struct see_pre_extension_expr **index_map;
  size_t pre_extension_num = htab_elements (see_pre_extension_hash);
  bool did_insert = false;
  int i;

  index_map = xcalloc (pre_extension_num,
                       sizeof (struct see_pre_extension_expr *));

  if (dump_file)
    fprintf (dump_file,
      "* Phase 4: Commit changes to the insn stream.  *\n");

  /* Produce a mapping of all the pre_extensions.  */
  htab_traverse (see_pre_extension_hash, see_map_extension, (PTR) index_map);

  /* Delete redundant extension.  This will prevent them from been emitted in
     the first place.  */
  htab_traverse (see_pre_extension_hash, see_pre_delete_extension, NULL);

  /* Insert extensions on edges, according to the LCM result.  */
  did_insert = see_pre_insert_extensions (index_map);

  if (did_insert)
    commit_edge_insertions ();

  /* Commit the rest of the changes.  */
  for (i = 0; i < last_bb; i++)
    {
      if (see_bb_splay_ar[i])
        {
          /* Traverse over all the references in the basic block in forward
             order.  */
          splay_tree_foreach (see_bb_splay_ar[i],
                              see_commit_ref_changes, NULL);
        }
    }

  free (index_map);
}


/* Phase 3 implementation: Eliminate globally redundant extensions.  */

/* Analyze the properties of a merged def extension for the LCM and record avail
   occurrences.

   This is a subroutine of see_analyze_ref_local_prop called
   via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_analyze_merged_def_local_prop (void **slot, void *b)
{
  rtx def_se = *slot;
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx ref = curr_ref_s->insn;
  struct see_pre_extension_expr *extension_expr;
  int indx;
  int bb_num = BLOCK_NUM (ref);
  htab_t curr_bb_hash;
  struct see_register_properties *curr_prop, **slot_prop;
  struct see_register_properties temp_prop;
  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
  struct see_occr *curr_occr = NULL;
  struct see_occr *tmp_occr = NULL;

  extension_expr = see_seek_pre_extension_expr (def_se, DEF_EXTENSION);
  /* The extension_expr must be found.  */
  gcc_assert (extension_expr);

  curr_bb_hash = see_bb_hash_ar[bb_num];
  gcc_assert (curr_bb_hash);
  temp_prop.regno = REGNO (dest_extension_reg);
  slot_prop =
    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
                                                        &temp_prop, INSERT);
  curr_prop = *slot_prop;
  gcc_assert (curr_prop);

  indx = extension_expr->bitmap_index;

  /* Reset the transparency bit.  */
  RESET_BIT (transp[bb_num], indx);
  /* Reset the killed bit.  */
  RESET_BIT (ae_kill[bb_num], indx);

  if (curr_prop->first_se_after_last_def == DF_INSN_LUID (ref))
    {
      /* Set the available bit.  */
      SET_BIT (comp[bb_num], indx);
      /* Record the available occurrence.  */
      curr_occr = xmalloc (sizeof (struct see_occr));
      curr_occr->next = NULL;
      curr_occr->insn = def_se;
      curr_occr->block_num = bb_num;
      tmp_occr = extension_expr->avail_occr;
      if (!tmp_occr)
        extension_expr->avail_occr = curr_occr;
      else
        {
          while (tmp_occr->next)
            tmp_occr = tmp_occr->next;
          tmp_occr->next = curr_occr;
        }
    }

  return 1;
}


/* Analyze the properties of a unmerged def extension for the LCM.

   This is a subroutine of see_analyze_ref_local_prop called
   via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_analyze_unmerged_def_local_prop (void **slot, void *b)
{
  rtx def_se = *slot;
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx ref = curr_ref_s->insn;
  struct see_pre_extension_expr *extension_expr;
  int indx;
  int bb_num = BLOCK_NUM (ref);
  htab_t curr_bb_hash;
  struct see_register_properties *curr_prop, **slot_prop;
  struct see_register_properties temp_prop;
  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);

  extension_expr = see_seek_pre_extension_expr (def_se, DEF_EXTENSION);
  /* The extension_expr must be found.  */
  gcc_assert (extension_expr);

  curr_bb_hash = see_bb_hash_ar[bb_num];
  gcc_assert (curr_bb_hash);
  temp_prop.regno = REGNO (dest_extension_reg);
  slot_prop =
    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
                                                        &temp_prop, INSERT);
  curr_prop = *slot_prop;
  gcc_assert (curr_prop);

  indx = extension_expr->bitmap_index;

  /* Reset the transparency bit.  */
  RESET_BIT (transp[bb_num], indx);
  /* Set the killed bit.  */
  SET_BIT (ae_kill[bb_num], indx);

  return 1;
}


/* Analyze the properties of a use extension for the LCM and record anic and
   avail occurrences.

   This is a subroutine of see_analyze_ref_local_prop called
   via htab_traverse.

   SLOT contains the current use extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_analyze_use_local_prop (void **slot, void *b)
{
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx use_se = *slot;
  rtx ref = curr_ref_s->insn;
  rtx dest_extension_reg = see_get_extension_reg (use_se, 1);
  struct see_pre_extension_expr *extension_expr;
  struct see_register_properties *curr_prop, **slot_prop;
  struct see_register_properties temp_prop;
  struct see_occr *curr_occr = NULL;
  struct see_occr *tmp_occr = NULL;
  htab_t curr_bb_hash;
  int indx;
  int bb_num = BLOCK_NUM (ref);

  extension_expr = see_seek_pre_extension_expr (use_se, USE_EXTENSION);
  /* The extension_expr must be found.  */
  gcc_assert (extension_expr);

  curr_bb_hash = see_bb_hash_ar[bb_num];
  gcc_assert (curr_bb_hash);
  temp_prop.regno = REGNO (dest_extension_reg);
  slot_prop =
    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
                                                        &temp_prop, INSERT);
  curr_prop = *slot_prop;
  gcc_assert (curr_prop);

  indx = extension_expr->bitmap_index;

  if (curr_prop->first_se_before_any_def == DF_INSN_LUID (ref))
    {
      /* Set the anticipatable bit.  */
      SET_BIT (antloc[bb_num], indx);
      /* Record the anticipatable occurrence.  */
      curr_occr = xmalloc (sizeof (struct see_occr));
      curr_occr->next = NULL;
      curr_occr->insn = use_se;
      curr_occr->block_num = bb_num;
      tmp_occr = extension_expr->antic_occr;
      if (!tmp_occr)
        extension_expr->antic_occr = curr_occr;
      else
        {
          while (tmp_occr->next)
            tmp_occr = tmp_occr->next;
          tmp_occr->next = curr_occr;
        }
      if (curr_prop->last_def < 0)
        {
          /* Set the available bit.  */
          SET_BIT (comp[bb_num], indx);
          /* Record the available occurrence.  */
          curr_occr = xmalloc (sizeof (struct see_occr));
          curr_occr->next = NULL;
          curr_occr->insn = use_se;
          curr_occr->block_num = bb_num;
          tmp_occr = extension_expr->avail_occr;
          if (!tmp_occr)
            extension_expr->avail_occr = curr_occr;
          else
            {
              while (tmp_occr->next)
                tmp_occr = tmp_occr->next;
              tmp_occr->next = curr_occr;
            }
        }
      /* Note: there is no need to reset the killed bit since it must be zero at
         this point.  */
    }
  else if (curr_prop->first_se_after_last_def == DF_INSN_LUID (ref))
    {
      /* Set the available bit.  */
      SET_BIT (comp[bb_num], indx);
      /* Reset the killed bit.  */
      RESET_BIT (ae_kill[bb_num], indx);
      /* Record the available occurrence.  */
      curr_occr = xmalloc (sizeof (struct see_occr));
      curr_occr->next = NULL;
      curr_occr->insn = use_se;
      curr_occr->block_num = bb_num;
      tmp_occr = extension_expr->avail_occr;
      if (!tmp_occr)
        extension_expr->avail_occr = curr_occr;
      else
        {
          while (tmp_occr->next)
            tmp_occr = tmp_occr->next;
          tmp_occr->next = curr_occr;
        }
    }
  return 1;
}


/* Here we traverse over all the merged and unmerged extensions of the reference
   and analyze their properties for the LCM.

   This is a subroutine of see_execute_LCM called via splay_tree_foreach.

   STN is the current node in the see_bb_splay_ar[i] splay tree.  It holds a
   see_ref_s structure.  */

static int
see_analyze_ref_local_prop (splay_tree_node stn,
                            void *data ATTRIBUTE_UNUSED)
{
  htab_t use_se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
  htab_t unmerged_def_se_hash =
    ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
  htab_t merged_def_se_hash =
    ((struct see_ref_s *) (stn->value))->merged_def_se_hash;

  /* Analyze use extensions that were not merged with the reference.  */
  if (use_se_hash)
    htab_traverse_noresize (use_se_hash, see_analyze_use_local_prop,
                            (PTR) (stn->value));

  /* Analyze def extensions that were not merged with the reference.  */
  if (unmerged_def_se_hash)
    htab_traverse (unmerged_def_se_hash, see_analyze_unmerged_def_local_prop,
                   (PTR) (stn->value));

  /* Analyze def extensions that were merged with the reference.  */
  if (merged_def_se_hash)
    htab_traverse (merged_def_se_hash, see_analyze_merged_def_local_prop,
                   (PTR) (stn->value));

  /* Continue to the next definition.  */
  return 0;
}


/* Phase 3 top level function.
   In this phase, we set the input bit vectors of the LCM according to data
   gathered in phase 2.
   Then we run the edge based LCM.  */

static void
see_execute_LCM (void)
{
  size_t pre_extension_num = htab_elements (see_pre_extension_hash);
  int i = 0;

  if (dump_file)
    fprintf (dump_file,
      "* Phase 3: Eliminate globally redundant extensions.  *\n");

  /* Initialize the global sbitmap vectors.  */
  transp = sbitmap_vector_alloc (last_bb, pre_extension_num);
  comp = sbitmap_vector_alloc (last_bb, pre_extension_num);
  antloc = sbitmap_vector_alloc (last_bb, pre_extension_num);
  ae_kill = sbitmap_vector_alloc (last_bb, pre_extension_num);
  sbitmap_vector_ones (transp, last_bb);
  sbitmap_vector_zero (comp, last_bb);
  sbitmap_vector_zero (antloc, last_bb);
  sbitmap_vector_zero (ae_kill, last_bb);

  /* Traverse over all the splay trees of the basic blocks.  */
  for (i = 0; i < last_bb; i++)
    {
      if (see_bb_splay_ar[i])
        {
          /* Traverse over all the references in the basic block in forward
             order.  */
          splay_tree_foreach (see_bb_splay_ar[i],
                              see_analyze_ref_local_prop, NULL);
        }
    }

  /* Add fake exit edges before running the lcm.  */
  add_noreturn_fake_exit_edges ();

  /* Run the LCM.  */
  edge_list = pre_edge_lcm (pre_extension_num, transp, comp, antloc,
                            ae_kill, &pre_insert_map, &pre_delete_map);

  /* Remove the fake edges.  */
  remove_fake_exit_edges ();
}


/* Phase 2 implementation: Merge and eliminate locally redundant extensions.  */

/* In this function we set the register properties for the register that is
   defined and extended in the reference.
   The properties are defined in see_register_properties structure which is
   allocated per basic block and per register.
   Later the extension is inserted into the see_pre_extension_hash for the next
   phase of the optimization.

   This is a subroutine of see_handle_extensions_for_one_ref called
   via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_set_prop_merged_def (void **slot, void *b)
{
  rtx def_se = *slot;
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx insn = curr_ref_s->insn;
  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
  htab_t curr_bb_hash;
  struct see_register_properties *curr_prop = NULL;
  struct see_register_properties **slot_prop;
  struct see_register_properties temp_prop;
  int ref_luid = DF_INSN_LUID (insn);

  curr_bb_hash = see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)];
  if (!curr_bb_hash)
    {
      /* The hash doesn't exist yet.  Create it.  */
      curr_bb_hash = htab_create (10, 
                                  hash_descriptor_properties, 
                                  eq_descriptor_properties,
                                  hash_del_properties);
      see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)] = curr_bb_hash;
    }

  /* Find the right register properties in the right basic block.  */
  temp_prop.regno = REGNO (dest_extension_reg);
  slot_prop =
    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
                                                        &temp_prop, INSERT);

  if (slot_prop && *slot_prop != NULL)
    {
      /* Property already exists.  */
      curr_prop = *slot_prop;
      gcc_assert (curr_prop->regno == REGNO (dest_extension_reg));

      curr_prop->last_def = ref_luid;
      curr_prop->first_se_after_last_def = ref_luid;
    }
  else
    {
      /* Property doesn't exist yet.  */
      curr_prop = xmalloc (sizeof (struct see_register_properties));
      curr_prop->regno = REGNO (dest_extension_reg);
      curr_prop->last_def = ref_luid;
      curr_prop->first_se_before_any_def = -1;
      curr_prop->first_se_after_last_def = ref_luid;
      *slot_prop = curr_prop;
    }

  /* Insert the def_se into see_pre_extension_hash if it isn't already
     there.  */
  see_seek_pre_extension_expr (def_se, DEF_EXTENSION);

  return 1;
}


/* In this function we set the register properties for the register that is
   defined but not extended in the reference.
   The properties are defined in see_register_properties structure which is
   allocated per basic block and per register.
   Later the extension is inserted into the see_pre_extension_hash for the next
   phase of the optimization.

   This is a subroutine of see_handle_extensions_for_one_ref called
   via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_set_prop_unmerged_def (void **slot, void *b)
{
  rtx def_se = *slot;
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx insn = curr_ref_s->insn;
  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
  htab_t curr_bb_hash;
  struct see_register_properties *curr_prop = NULL;
  struct see_register_properties **slot_prop;
  struct see_register_properties temp_prop;
  int ref_luid = DF_INSN_LUID (insn);

  curr_bb_hash = see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)];
  if (!curr_bb_hash)
    {
      /* The hash doesn't exist yet.  Create it.  */
      curr_bb_hash = htab_create (10, 
                                  hash_descriptor_properties, 
                                  eq_descriptor_properties,
                                  hash_del_properties);
      see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)] = curr_bb_hash;
    }

  /* Find the right register properties in the right basic block.  */
  temp_prop.regno = REGNO (dest_extension_reg);
  slot_prop =
    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
                                                        &temp_prop, INSERT);

  if (slot_prop && *slot_prop != NULL)
    {
      /* Property already exists.  */
      curr_prop = *slot_prop;
      gcc_assert (curr_prop->regno == REGNO (dest_extension_reg));

      curr_prop->last_def = ref_luid;
      curr_prop->first_se_after_last_def = -1;
    }
  else
    {
      /* Property doesn't exist yet.  */
      curr_prop = xmalloc (sizeof (struct see_register_properties));
      curr_prop->regno = REGNO (dest_extension_reg);
      curr_prop->last_def = ref_luid;
      curr_prop->first_se_before_any_def = -1;
      curr_prop->first_se_after_last_def = -1;
      *slot_prop = curr_prop;
    }

  /* Insert the def_se into see_pre_extension_hash if it isn't already
     there.  */
  see_seek_pre_extension_expr (def_se, DEF_EXTENSION);

  return 1;
}


/* In this function we set the register properties for the register that is used
   in the reference.
   The properties are defined in see_register_properties structure which is
   allocated per basic block and per register.
   When a redundant use extension is found it is removed from the hash of the
   reference.
   If the extension is non redundant it is inserted into the
   see_pre_extension_hash for the next phase of the optimization.

   This is a subroutine of see_handle_extensions_for_one_ref called
   via htab_traverse.

   SLOT contains the current use extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_set_prop_unmerged_use (void **slot, void *b)
{
  rtx use_se = *slot;
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx insn = curr_ref_s->insn;
  rtx dest_extension_reg = see_get_extension_reg (use_se, 1);
  htab_t curr_bb_hash;
  struct see_register_properties *curr_prop = NULL;
  struct see_register_properties **slot_prop;
  struct see_register_properties temp_prop;
  bool locally_redundant = false;
  int ref_luid = DF_INSN_LUID (insn);

  curr_bb_hash = see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)];
  if (!curr_bb_hash)
    {
      /* The hash doesn't exist yet.  Create it.  */
      curr_bb_hash = htab_create (10, 
                                  hash_descriptor_properties, 
                                  eq_descriptor_properties,
                                  hash_del_properties);
      see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)] = curr_bb_hash;
    }

  /* Find the right register properties in the right basic block.  */
  temp_prop.regno = REGNO (dest_extension_reg);
  slot_prop =
    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
                                                        &temp_prop, INSERT);

  if (slot_prop && *slot_prop != NULL)
    {
      /* Property already exists.  */
      curr_prop = *slot_prop;
      gcc_assert (curr_prop->regno == REGNO (dest_extension_reg));


      if (curr_prop->last_def < 0 && curr_prop->first_se_before_any_def < 0)
        curr_prop->first_se_before_any_def = ref_luid;
      else if (curr_prop->last_def < 0
               && curr_prop->first_se_before_any_def >= 0)
        {
          /* In this case the extension is locally redundant.  */
          htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
          locally_redundant = true;
        }
      else if (curr_prop->last_def >= 0
               && curr_prop->first_se_after_last_def < 0)
        curr_prop->first_se_after_last_def = ref_luid;
      else if (curr_prop->last_def >= 0
               && curr_prop->first_se_after_last_def >= 0)
        {
          /* In this case the extension is locally redundant.  */
          htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
          locally_redundant = true;
        }
      else
        gcc_unreachable ();
    }
  else
    {
      /* Property doesn't exist yet.  Create a new one.  */
      curr_prop = xmalloc (sizeof (struct see_register_properties));
      curr_prop->regno = REGNO (dest_extension_reg);
      curr_prop->last_def = -1;
      curr_prop->first_se_before_any_def = ref_luid;
      curr_prop->first_se_after_last_def = -1;
      *slot_prop = curr_prop;
    }

  /* Insert the use_se into see_pre_extension_hash if it isn't already
     there.  */
  if (!locally_redundant)
    see_seek_pre_extension_expr (use_se, USE_EXTENSION);
  if (locally_redundant && dump_file)
    {
      fprintf (dump_file, "Locally redundant extension:\n");
      print_rtl_single (dump_file, use_se);
    }
  return 1;
}


/* Print an extension instruction.

   This is a subroutine of see_handle_extensions_for_one_ref called
   via htab_traverse.
   SLOT contains the extension instruction.  */

static int
see_print_one_extension (void **slot, void *b ATTRIBUTE_UNUSED)
{
  rtx def_se = *slot;

  gcc_assert (def_se && INSN_P (def_se));
  print_rtl_single (dump_file, def_se);

  return 1;
}

/* Function called by note_uses to replace used subexpressions.

   X is a pointer to the subexpression and DATA is a pointer to a
   see_replace_data structure that contains the data for the replacement.  */

static void
see_replace_src (rtx *x, void *data)
{
  struct see_replace_data *d
    = (struct see_replace_data *) data;

  *x = replace_rtx (*x, d->from, d->to);
}


static rtx
see_copy_insn (rtx insn)
{
  rtx pat = copy_insn (PATTERN (insn)), ret;

  if (NONJUMP_INSN_P (insn))
    ret = make_insn_raw (pat);
  else if (JUMP_P (insn))
    ret = make_jump_insn_raw (pat);
  else if (CALL_P (insn))
    {
      start_sequence ();
      ret = emit_call_insn (pat);
      end_sequence ();
      if (CALL_INSN_FUNCTION_USAGE (insn))
        CALL_INSN_FUNCTION_USAGE (ret)
          = copy_rtx (CALL_INSN_FUNCTION_USAGE (insn));
      SIBLING_CALL_P (ret) = SIBLING_CALL_P (insn);
      RTL_CONST_CALL_P (ret) = RTL_CONST_CALL_P (insn);
      RTL_PURE_CALL_P (ret) = RTL_PURE_CALL_P (insn);
      RTL_LOOPING_CONST_OR_PURE_CALL_P (ret) 
        = RTL_LOOPING_CONST_OR_PURE_CALL_P (insn);
    }
  else
    gcc_unreachable ();
  if (REG_NOTES (insn))
    REG_NOTES (ret) = copy_rtx (REG_NOTES (insn));
  INSN_LOCATOR (ret) = INSN_LOCATOR (insn);
  RTX_FRAME_RELATED_P (ret) = RTX_FRAME_RELATED_P (insn);
  PREV_INSN (ret) = NULL_RTX;
  NEXT_INSN (ret) = NULL_RTX;
  return ret;
}


/* At this point the pattern is expected to be:

   ref:     set (dest_reg) (rhs)
   def_se:  set (dest_extension_reg) (sign/zero_extend (source_extension_reg))

   The merge of these two instructions didn't succeed.

   We try to generate the pattern:
   set (subreg (dest_extension_reg)) (rhs)

   We do this in 4 steps:
   a. Replace every use of dest_reg with a new pseudo register.
   b. Replace every instance of dest_reg with the subreg.
   c. Replace every use of the new pseudo register back to dest_reg.
   d. Try to recognize and simplify.

   If the manipulation failed, leave the original ref but try to generate and
   recognize a simple move instruction:
   set (subreg (dest_extension_reg)) (dest_reg)
   This move instruction will be emitted right after the ref to the instruction
   stream and assure the correctness of the code after def_se will be removed.

   CURR_REF_S is the current reference.
   DEF_SE is the extension that couldn't be merged.  */

static void
see_def_extension_not_merged (struct see_ref_s *curr_ref_s, rtx def_se)
{
  struct see_replace_data d;
  /* If the original insn was already merged with an extension before,
     take the merged one.  */
  rtx ref = curr_ref_s->merged_insn
            ? curr_ref_s->merged_insn : curr_ref_s->insn;
  rtx merged_ref_next = curr_ref_s->merged_insn
                        ? NEXT_INSN (curr_ref_s->merged_insn) : NULL_RTX;
  rtx ref_copy = see_copy_insn (ref);
  rtx source_extension_reg = see_get_extension_reg (def_se, 0);
  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
  rtx set, rhs;
  rtx dest_reg, dest_real_reg;
  rtx new_pseudo_reg, subreg;
  enum machine_mode source_extension_mode = GET_MODE (source_extension_reg);
  enum machine_mode dest_mode;

  set = single_set (def_se);
  gcc_assert (set);
  rhs = SET_SRC (set);
  gcc_assert (GET_CODE (rhs) == SIGN_EXTEND
              || GET_CODE (rhs) == ZERO_EXTEND);
  dest_reg = XEXP (rhs, 0);
  gcc_assert (REG_P (dest_reg)
              || (GET_CODE (dest_reg) == SUBREG
                  && REG_P (SUBREG_REG (dest_reg))));
  dest_real_reg = REG_P (dest_reg) ? dest_reg : SUBREG_REG (dest_reg);
  dest_mode = GET_MODE (dest_reg);

  subreg = gen_lowpart_SUBREG (dest_mode, dest_extension_reg);
  new_pseudo_reg = gen_reg_rtx (source_extension_mode);

  /* Step a: Replace every use of dest_real_reg with a new pseudo register.  */
  d.from = dest_real_reg;
  d.to = new_pseudo_reg;
  note_uses (&PATTERN (ref_copy), see_replace_src, &d);
  /* Step b: Replace every instance of dest_reg with the subreg.  */
  ref_copy = replace_rtx (ref_copy, dest_reg, copy_rtx (subreg));

  /* Step c: Replace every use of the new pseudo register back to
     dest_real_reg.  */
  d.from = new_pseudo_reg;
  d.to = dest_real_reg;
  note_uses (&PATTERN (ref_copy), see_replace_src, &d);

  if (rtx_equal_p (PATTERN (ref), PATTERN (ref_copy))
      || insn_invalid_p (ref_copy))
    {
      /* The manipulation failed.  */
      df_insn_delete (NULL, INSN_UID (ref_copy));

      /* Create a new copy.  */
      ref_copy = see_copy_insn (ref);

      if (curr_ref_s->merged_insn)
        df_insn_delete (NULL, INSN_UID (curr_ref_s->merged_insn));

      /* Create a simple move instruction that will replace the def_se.  */
      start_sequence ();
      emit_insn (ref_copy);
      emit_move_insn (subreg, dest_reg);
      if (merged_ref_next != NULL_RTX)
        emit_insn (merged_ref_next);
      curr_ref_s->merged_insn = get_insns ();
      end_sequence ();

      if (dump_file)
        {
          fprintf (dump_file, "Following def merge failure a move ");
          fprintf (dump_file, "insn was added after the ref.\n");
          fprintf (dump_file, "Original ref:\n");
          print_rtl_single (dump_file, ref);
          fprintf (dump_file, "Move insn that was added:\n");
          print_rtl_single (dump_file, NEXT_INSN (curr_ref_s->merged_insn));
        }
      return;
    }

  /* The manipulation succeeded.  Store the new manipulated reference.  */

  /* Try to simplify the new manipulated insn.  */
  validate_simplify_insn (ref_copy);

  if (curr_ref_s->merged_insn)
    df_insn_delete (NULL, INSN_UID (curr_ref_s->merged_insn));

  /* Create a simple move instruction to assure the correctness of the code.  */
  start_sequence ();
  emit_insn (ref_copy);
  emit_move_insn (dest_reg, subreg);
  if (merged_ref_next != NULL_RTX)
    emit_insn (merged_ref_next);
  curr_ref_s->merged_insn = get_insns ();
  end_sequence ();

  if (dump_file)
    {
      fprintf (dump_file, "Following merge failure the ref was transformed!\n");
      fprintf (dump_file, "Original ref:\n");
      print_rtl_single (dump_file, ref);
      fprintf (dump_file, "Transformed ref:\n");
      print_rtl_single (dump_file, curr_ref_s->merged_insn);
      fprintf (dump_file, "Move insn that was added:\n");
      print_rtl_single (dump_file, NEXT_INSN (curr_ref_s->merged_insn));
    }
}


/* Merge the reference instruction (ref) with the current use extension.

   use_se extends a NARROWmode register to a WIDEmode register.
   ref uses the WIDEmode register.

   The pattern we try to merge is this:
   use_se: set (dest_extension_reg) (sign/zero_extend (source_extension_reg))
   ref:    use (dest_extension_reg)

   where dest_extension_reg and source_extension_reg can be subregs.

   The merge is done by generating, simplifying and recognizing the pattern:
   use (sign/zero_extend (source_extension_reg))

   If ref is too simple (according to see_want_to_be_merged_with_extension ())
   we don't try to merge it with use_se and we continue as if the merge failed.

   This is a subroutine of see_handle_extensions_for_one_ref called
   via htab_traverse.
   SLOT contains the current use extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_merge_one_use_extension (void **slot, void *b)
{
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx use_se = *slot;
  rtx ref = curr_ref_s->merged_insn
            ? curr_ref_s->merged_insn : curr_ref_s->insn;
  rtx merged_ref_next = curr_ref_s->merged_insn
                        ? NEXT_INSN (curr_ref_s->merged_insn) : NULL_RTX;
  rtx ref_copy = see_copy_insn (ref);
  rtx extension_set = single_set (use_se);
  rtx extension_rhs = NULL;
  rtx dest_extension_reg = see_get_extension_reg (use_se, 1);
  rtx note = NULL;
  rtx simplified_note = NULL;

  gcc_assert (use_se && curr_ref_s && extension_set);

  extension_rhs = SET_SRC (extension_set);

  /* In REG_EQUIV and REG_EQUAL notes that mention the register we need to
     replace the uses of the dest_extension_reg with the rhs of the extension
     instruction.  This is necessary since there might not be an extension in
     the path between the definition and the note when this optimization is
     over.  */
  note = find_reg_equal_equiv_note (ref_copy);
  if (note)
    {
      simplified_note = simplify_replace_rtx (XEXP (note, 0),
                                              dest_extension_reg,
                                              extension_rhs);
      if (rtx_equal_p (XEXP (note, 0), simplified_note))
        /* Replacement failed.  Remove the note.  */
        remove_note (ref_copy, note);
      else
        set_unique_reg_note (ref_copy, REG_NOTE_KIND (note),
                             simplified_note);
    }

  if (!see_want_to_be_merged_with_extension (ref, use_se, USE_EXTENSION))
    {
      /* The use in the reference is too simple.  Don't try to merge.  */
      if (dump_file)
        {
          fprintf (dump_file, "Use merge skipped!\n");
          fprintf (dump_file, "Original instructions:\n");
          print_rtl_single (dump_file, use_se);
          print_rtl_single (dump_file, ref);
        }
      df_insn_delete (NULL, INSN_UID (ref_copy));
      /* Don't remove the current use_se from the use_se_hash and continue to
         the next extension.  */
      return 1;
    }

  validate_replace_src_group (dest_extension_reg, extension_rhs, ref_copy);

  if (!num_changes_pending ())
    /* In this case this is not a real use (the only use is/was in the notes
       list).  Remove the use extension from the hash.  This will prevent it
       from been emitted in the first place.  */
    {
      if (dump_file)
        {
          fprintf (dump_file, "Use extension not necessary before:\n");
          print_rtl_single (dump_file, ref);
        }
      htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);

      if (curr_ref_s->merged_insn)
        df_insn_delete (NULL, INSN_UID (curr_ref_s->merged_insn));

      if (merged_ref_next != NULL_RTX)
        {
          start_sequence ();
          emit_insn (ref_copy);
          emit_insn (merged_ref_next);
          curr_ref_s->merged_insn = get_insns ();
          end_sequence ();
        }
      else
        curr_ref_s->merged_insn = ref_copy;
      return 1;
    }

  if (!apply_change_group ())
    {
      /* The merge failed.  */
      if (dump_file)
        {
          fprintf (dump_file, "Use merge failed!\n");
          fprintf (dump_file, "Original instructions:\n");
          print_rtl_single (dump_file, use_se);
          print_rtl_single (dump_file, ref);
        }
      df_insn_delete (NULL, INSN_UID (ref_copy));
      /* Don't remove the current use_se from the use_se_hash and continue to
         the next extension.  */
      return 1;
    }

  /* The merge succeeded!  */

  /* Try to simplify the new merged insn.  */
  validate_simplify_insn (ref_copy);

  if (curr_ref_s->merged_insn)
    df_insn_delete (NULL, INSN_UID (curr_ref_s->merged_insn));

  if (merged_ref_next != NULL_RTX)
    {
      start_sequence ();
      emit_insn (ref_copy);
      emit_insn (merged_ref_next);
      curr_ref_s->merged_insn = get_insns ();
      end_sequence ();
    }
  else
    curr_ref_s->merged_insn = ref_copy;

  if (dump_file)
    {
      fprintf (dump_file, "Use merge succeeded!\n");
      fprintf (dump_file, "Original instructions:\n");
      print_rtl_single (dump_file, use_se);
      print_rtl_single (dump_file, ref);
      fprintf (dump_file, "Merged instruction:\n");
      print_rtl_single (dump_file, curr_ref_s->merged_insn);
    }

  /* Remove the current use_se from the use_se_hash.  This will prevent it from
     been emitted in the first place.  */
  htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
  return 1;
}


/* Merge the reference instruction (ref) with the extension that follows it
   in the same basic block (def_se).
   ref sets a NARROWmode register and def_se extends it to WIDEmode register.

   The pattern we try to merge is this:
   ref:    set (dest_reg) (rhs)
   def_se: set (dest_extension_reg) (sign/zero_extend (source_extension_reg))

   where dest_reg and source_extension_reg can both be subregs (together)
   and (REGNO (dest_reg) == REGNO (source_extension_reg))

   The merge is done by generating, simplifying and recognizing the pattern:
   set (dest_extension_reg) (sign/zero_extend (rhs))
   If ref is a parallel instruction we just replace the relevant set in it.

   If ref is too simple (according to see_want_to_be_merged_with_extension ())
   we don't try to merge it with def_se and we continue as if the merge failed.

   This is a subroutine of see_handle_extensions_for_one_ref called
   via htab_traverse.

   SLOT contains the current def extension instruction.
   B is the see_ref_s structure pointer.  */

static int
see_merge_one_def_extension (void **slot, void *b)
{
  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
  rtx def_se = *slot;
  /* If the original insn was already merged with an extension before,
     take the merged one.  */
  rtx ref = curr_ref_s->merged_insn
            ? curr_ref_s->merged_insn : curr_ref_s->insn;
  rtx merged_ref_next = curr_ref_s->merged_insn
                        ? NEXT_INSN (curr_ref_s->merged_insn) : NULL_RTX;
  rtx ref_copy = see_copy_insn (ref);
  rtx new_set = NULL;
  rtx source_extension_reg = see_get_extension_reg (def_se, 0);
  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
  rtx *rtx_slot, subreg;
  rtx temp_extension = NULL;
  rtx simplified_temp_extension = NULL;
  rtx *pat;
  enum rtx_code code;
  enum rtx_code extension_code;
  enum machine_mode source_extension_mode;
  enum machine_mode source_mode;
  enum machine_mode dest_extension_mode;
  bool merge_success = false;
  int i;

  gcc_assert (def_se
              && INSN_P (def_se)
              && curr_ref_s
              && ref
              && INSN_P (ref));

  if (!see_want_to_be_merged_with_extension (ref, def_se, DEF_EXTENSION))
    {
      /* The definition in the reference is too simple.  Don't try to merge.  */
      if (dump_file)
        {
          fprintf (dump_file, "Def merge skipped!\n");
          fprintf (dump_file, "Original instructions:\n");
          print_rtl_single (dump_file, ref);
          print_rtl_single (dump_file, def_se);
        }

      df_insn_delete (NULL, INSN_UID (ref_copy));
      see_def_extension_not_merged (curr_ref_s, def_se);
      /* Continue to the next extension.  */
      return 1;
    }

  extension_code = see_get_extension_data (def_se, &source_mode);

  /* Try to merge and simplify the extension.  */
  source_extension_mode = GET_MODE (source_extension_reg);
  dest_extension_mode = GET_MODE (dest_extension_reg);

  pat = &PATTERN (ref_copy);
  code = GET_CODE (*pat);

  if (code == PARALLEL)
    {
      bool need_to_apply_change = false;

      for (i = 0; i < XVECLEN (*pat, 0); i++)
        {
          rtx *sub = &XVECEXP (*pat, 0, i);

          if (GET_CODE (*sub) == SET
              && GET_MODE (SET_SRC (*sub)) != VOIDmode
              && GET_MODE (SET_DEST (*sub)) == source_mode
              && ((REG_P (SET_DEST (*sub))
                   && REGNO (SET_DEST (*sub)) == REGNO (source_extension_reg))
                  || (GET_CODE (SET_DEST (*sub)) == SUBREG
                      && REG_P (SUBREG_REG (SET_DEST (*sub)))
                      && (REGNO (SUBREG_REG (SET_DEST (*sub))) ==
                          REGNO (source_extension_reg)))))
            {
              rtx orig_src = SET_SRC (*sub);

              if (extension_code == SIGN_EXTEND)
                temp_extension = gen_rtx_SIGN_EXTEND (dest_extension_mode,
                                                      orig_src);
              else
                temp_extension = gen_rtx_ZERO_EXTEND (dest_extension_mode,
                                                      orig_src);
              simplified_temp_extension = simplify_rtx (temp_extension);
              temp_extension =
                (simplified_temp_extension) ? simplified_temp_extension :
                                              temp_extension;
              new_set = gen_rtx_SET (VOIDmode, dest_extension_reg,
                                     temp_extension);
              validate_change (ref_copy, sub, new_set, 1);
              need_to_apply_change = true;
            }
        }
      if (need_to_apply_change)
        if (apply_change_group ())
          merge_success = true;
    }
  else if (code == SET
           && GET_MODE (SET_SRC (*pat)) != VOIDmode
           && GET_MODE (SET_DEST (*pat)) == source_mode
           && ((REG_P (SET_DEST (*pat))
                && REGNO (SET_DEST (*pat)) == REGNO (source_extension_reg))
               || (GET_CODE (SET_DEST (*pat)) == SUBREG
                   && REG_P (SUBREG_REG (SET_DEST (*pat)))
                   && (REGNO (SUBREG_REG (SET_DEST (*pat))) ==
                       REGNO (source_extension_reg)))))
    {
      rtx orig_src = SET_SRC (*pat);

      if (extension_code == SIGN_EXTEND)
        temp_extension = gen_rtx_SIGN_EXTEND (dest_extension_mode, orig_src);
      else
        temp_extension = gen_rtx_ZERO_EXTEND (dest_extension_mode, orig_src);
      simplified_temp_extension = simplify_rtx (temp_extension);
      temp_extension = (simplified_temp_extension) ? simplified_temp_extension :
                                                     temp_extension;
      new_set = gen_rtx_SET (VOIDmode, dest_extension_reg, temp_extension);
      if (validate_change (ref_copy, pat, new_set, 0))
        merge_success = true;
    }
  if (!merge_success)
    {
      /* The merge failed.  */
      if (dump_file)
        {
          fprintf (dump_file, "Def merge failed!\n");
          fprintf (dump_file, "Original instructions:\n");
          print_rtl_single (dump_file, ref);
          print_rtl_single (dump_file, def_se);
        }

      df_insn_delete (NULL, INSN_UID (ref_copy));
      see_def_extension_not_merged (curr_ref_s, def_se);
      /* Continue to the next extension.  */
      return 1;
    }

  /* The merge succeeded!  */
  if (curr_ref_s->merged_insn)
    df_insn_delete (NULL, INSN_UID (curr_ref_s->merged_insn));

  /* Create a simple move instruction to assure the correctness of the code.  */
  subreg = gen_lowpart_SUBREG (source_extension_mode, dest_extension_reg);
  start_sequence ();
  emit_insn (ref_copy);
  emit_move_insn (source_extension_reg, subreg);
  if (merged_ref_next != NULL_RTX)
    emit_insn (merged_ref_next);
  curr_ref_s->merged_insn = get_insns ();
  end_sequence ();

  if (dump_file)
    {
      fprintf (dump_file, "Def merge succeeded!\n");
      fprintf (dump_file, "Original instructions:\n");
      print_rtl_single (dump_file, ref);
      print_rtl_single (dump_file, def_se);
      fprintf (dump_file, "Merged instruction:\n");
      print_rtl_single (dump_file, curr_ref_s->merged_insn);
      fprintf (dump_file, "Move instruction that was added:\n");
      print_rtl_single (dump_file, NEXT_INSN (curr_ref_s->merged_insn));
    }

  /* Remove the current def_se from the unmerged_def_se_hash and insert it to
     the merged_def_se_hash.  */
  htab_clear_slot (curr_ref_s->unmerged_def_se_hash, (PTR *)slot);
  if (!curr_ref_s->merged_def_se_hash)
    curr_ref_s->merged_def_se_hash = htab_create (10, 
                                                  hash_descriptor_extension, 
                                                  eq_descriptor_extension,
                                                  NULL);
  rtx_slot = (rtx *) htab_find_slot (curr_ref_s->merged_def_se_hash,
                                     dest_extension_reg, INSERT);
  gcc_assert (*rtx_slot == NULL);
  *rtx_slot = def_se;

  return 1;
}


/* Try to eliminate extensions in this order:
   a. Try to merge only the def extensions, one by one.
   b. Try to merge only the use extensions, one by one.

   TODO:
   Try to merge any couple of use extensions simultaneously.
   Try to merge any def extension with one or two uses extensions
   simultaneously.

   After all the merges are done, update the register properties for the basic
   block and eliminate locally redundant use extensions.

   This is a subroutine of see_merge_and_eliminate_extensions called
   via splay_tree_foreach.
   STN is the current node in the see_bb_splay_ar[i] splay tree.  It holds a
   see_ref_s structure.  */

static int
see_handle_extensions_for_one_ref (splay_tree_node stn,
                                   void *data ATTRIBUTE_UNUSED)
{
  htab_t use_se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
  htab_t unmerged_def_se_hash =
    ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
  htab_t merged_def_se_hash;
  rtx ref = ((struct see_ref_s *) (stn->value))->insn;

  if (dump_file)
    {
      fprintf (dump_file, "Handling ref:\n");
      print_rtl_single (dump_file, ref);
    }

  /* a. Try to eliminate only def extensions, one by one.  */
  if (unmerged_def_se_hash)
    htab_traverse_noresize (unmerged_def_se_hash, see_merge_one_def_extension,
                            (PTR) (stn->value));

  if (use_se_hash)
    /* b. Try to eliminate only use extensions, one by one.  */
    htab_traverse_noresize (use_se_hash, see_merge_one_use_extension,
                            (PTR) (stn->value));

  merged_def_se_hash = ((struct see_ref_s *) (stn->value))->merged_def_se_hash;

  if (dump_file)
    {
      fprintf (dump_file, "The hashes of the current reference:\n");
      if (unmerged_def_se_hash)
        {
          fprintf (dump_file, "unmerged_def_se_hash:\n");
          htab_traverse (unmerged_def_se_hash, see_print_one_extension, NULL);
        }
      if (merged_def_se_hash)
        {
          fprintf (dump_file, "merged_def_se_hash:\n");
          htab_traverse (merged_def_se_hash, see_print_one_extension, NULL);
        }
      if (use_se_hash)
        {
          fprintf (dump_file, "use_se_hash:\n");
          htab_traverse (use_se_hash, see_print_one_extension, NULL);
        }
    }

  /* Now that all the merges are done, update the register properties of the
     basic block and eliminate locally redundant extensions.
     It is important that we first traverse the use extensions hash and
     afterwards the def extensions hashes.  */

  if (use_se_hash)
    htab_traverse_noresize (use_se_hash, see_set_prop_unmerged_use,
                            (PTR) (stn->value));

  if (unmerged_def_se_hash)
    htab_traverse (unmerged_def_se_hash, see_set_prop_unmerged_def,
                   (PTR) (stn->value));

  if (merged_def_se_hash)
    htab_traverse (merged_def_se_hash, see_set_prop_merged_def,
                   (PTR) (stn->value));

  /* Continue to the next definition.  */
  return 0;
}


/* Phase 2 top level function.
   In this phase, we try to merge def extensions and use extensions with their
   references, and eliminate redundant extensions in the same basic block.  
   We also gather information for the next phases.  */

static void
see_merge_and_eliminate_extensions (void)
{
  int i = 0;

  if (dump_file)
    fprintf (dump_file,
      "* Phase 2: Merge and eliminate locally redundant extensions.  *\n");

  /* Traverse over all the splay trees of the basic blocks.  */
  for (i = 0; i < last_bb; i++)
    {
      if (see_bb_splay_ar[i])
        {
          if (dump_file)
            fprintf (dump_file, "Handling references for bb %d\n", i);
          /* Traverse over all the references in the basic block in forward
             order.  */
          splay_tree_foreach (see_bb_splay_ar[i],
                              see_handle_extensions_for_one_ref, NULL);
        }
    }
}


/* Phase 1 implementation: Propagate extensions to uses.  */

/* Insert REF_INSN into the splay tree of its basic block.
   SE_INSN is the extension to store in the proper hash according to TYPE.

   Return true if everything went well.
   Otherwise, return false (this will cause the optimization to be aborted).  */

static bool
see_store_reference_and_extension (rtx ref_insn, rtx se_insn,
                                   enum extension_type type)
{
  rtx *rtx_slot;
  int curr_bb_num;
  splay_tree_node stn = NULL;
  htab_t se_hash = NULL;
  struct see_ref_s *ref_s = NULL;

  /* Check the arguments.  */
  gcc_assert (ref_insn && se_insn);
  if (!see_bb_splay_ar)
    return false;

  curr_bb_num = BLOCK_NUM (ref_insn);
  gcc_assert (curr_bb_num < last_bb && curr_bb_num >= 0);

  /* Insert the reference to the splay tree of its basic block.  */
  if (!see_bb_splay_ar[curr_bb_num])
    /* The splay tree for this block doesn't exist yet, create it.  */
    see_bb_splay_ar[curr_bb_num] = splay_tree_new (splay_tree_compare_ints,
                                                    NULL, see_free_ref_s);
  else
    /* Splay tree already exists, check if the current reference is already
       in it.  */
    {
      stn = splay_tree_lookup (see_bb_splay_ar[curr_bb_num],
                               DF_INSN_LUID (ref_insn));
      if (stn)
        switch (type)
          {
          case EXPLICIT_DEF_EXTENSION:
            se_hash =
              ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
            if (!se_hash)
              {
                se_hash = htab_create (10, 
                                       hash_descriptor_extension,
                                       eq_descriptor_extension, 
                                       NULL);
                ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash =
                  se_hash;
              }
            break;
          case IMPLICIT_DEF_EXTENSION:
            se_hash = ((struct see_ref_s *) (stn->value))->merged_def_se_hash;
            if (!se_hash)
              {
                se_hash = htab_create (10, 
                                       hash_descriptor_extension,
                                       eq_descriptor_extension, 
                                       NULL);
                ((struct see_ref_s *) (stn->value))->merged_def_se_hash =
                  se_hash;
              }
            break;
          case USE_EXTENSION:
            se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
            if (!se_hash)
              {
                se_hash = htab_create (10, 
                                       hash_descriptor_extension,
                                       eq_descriptor_extension, 
                                       NULL);
                ((struct see_ref_s *) (stn->value))->use_se_hash = se_hash;
              }
            break;
          default:
            gcc_unreachable ();
          }
    }

  /* Initialize a new see_ref_s structure and insert it to the splay
     tree.  */
  if (!stn)
    {
      ref_s = xmalloc (sizeof (struct see_ref_s));
      ref_s->luid = DF_INSN_LUID (ref_insn);
      ref_s->insn = ref_insn;
      ref_s->merged_insn = NULL;

      /* Initialize the hashes.  */
      switch (type)
        {
        case EXPLICIT_DEF_EXTENSION:
          ref_s->unmerged_def_se_hash = htab_create (10, 
                                                     hash_descriptor_extension, 
                                                     eq_descriptor_extension,
                                                     NULL);
          se_hash = ref_s->unmerged_def_se_hash;
          ref_s->merged_def_se_hash = NULL;
          ref_s->use_se_hash = NULL;
          break;
        case IMPLICIT_DEF_EXTENSION:
          ref_s->merged_def_se_hash = htab_create (10, 
                                                   hash_descriptor_extension, 
                                                   eq_descriptor_extension,
                                                   NULL);
          se_hash = ref_s->merged_def_se_hash;
          ref_s->unmerged_def_se_hash = NULL;
          ref_s->use_se_hash = NULL;
          break;
        case USE_EXTENSION:
          ref_s->use_se_hash = htab_create (10, 
                                            hash_descriptor_extension, 
                                            eq_descriptor_extension,
                                            NULL);
          se_hash = ref_s->use_se_hash;
          ref_s->unmerged_def_se_hash = NULL;
          ref_s->merged_def_se_hash = NULL;
          break;
        default:
          gcc_unreachable ();
        }
    }

  /* Insert the new extension instruction into the correct se_hash of the
     current reference.  */
  rtx_slot = (rtx *) htab_find_slot (se_hash, se_insn, INSERT);
  if (*rtx_slot != NULL)
    {
      gcc_assert (type == USE_EXTENSION);
      gcc_assert (rtx_equal_p (PATTERN (*rtx_slot), PATTERN (se_insn)));
    }
  else
    *rtx_slot = se_insn;

  /* If this is a new reference, insert it into the splay_tree.  */
  if (!stn)
    splay_tree_insert (see_bb_splay_ar[curr_bb_num],
                       DF_INSN_LUID (ref_insn), (splay_tree_value) ref_s);
  return true;
}


/* Go over all the defs, for each relevant definition (defined below) store its
   instruction as a reference.

   A definition is relevant if its root has
   ((entry_type == SIGN_EXTENDED_DEF) || (entry_type == ZERO_EXTENDED_DEF)) and
   his source_mode is not narrower then the roots source_mode.

   Return the number of relevant defs or negative number if something bad had
   happened and the optimization should be aborted.  */

static int
see_handle_relevant_defs (struct df_ref *ref, rtx insn)
{
  struct web_entry *root_entry = NULL;
  rtx se_insn = NULL;
  enum rtx_code extension_code;
  rtx reg = DF_REF_REAL_REG (ref);
  rtx ref_insn = NULL;
  unsigned int i = DF_REF_ID (ref);

  root_entry = unionfind_root (&def_entry[DF_REF_ID (ref)]);

  if (ENTRY_EI (root_entry)->relevancy != SIGN_EXTENDED_DEF
      && ENTRY_EI (root_entry)->relevancy != ZERO_EXTENDED_DEF)
    /* The current web is not relevant.  Continue to the next def.  */
    return 0;
  
  if (root_entry->reg)
    /* It isn't possible to have two different register for the same
       web.  */
    gcc_assert (rtx_equal_p (root_entry->reg, reg));
  else
    root_entry->reg = reg;
  
  /* The current definition is an EXTENDED_DEF or a definition that its
     source_mode is narrower then its web's source_mode.
     This means that we need to generate the implicit extension explicitly
     and store it in the current reference's merged_def_se_hash.  */
  if (ENTRY_EI (&def_entry[i])->local_relevancy == EXTENDED_DEF
      || (ENTRY_EI (&def_entry[i])->local_source_mode <
          ENTRY_EI (root_entry)->source_mode))
    {
      
      if (ENTRY_EI (root_entry)->relevancy == SIGN_EXTENDED_DEF)
        extension_code = SIGN_EXTEND;
      else
        extension_code = ZERO_EXTEND;
      
      se_insn =
        see_gen_normalized_extension (reg, extension_code,
                                      ENTRY_EI (root_entry)->source_mode);
      
      /* This is a dummy extension, mark it as deleted.  */
      INSN_DELETED_P (se_insn) = 1;
      
      if (!see_store_reference_and_extension (insn, se_insn,
                                              IMPLICIT_DEF_EXTENSION))
        /* Something bad happened.  Abort the optimization.  */
        return -1;
      return 1;
    }
  
  ref_insn = PREV_INSN (insn);
  gcc_assert (BLOCK_NUM (ref_insn) == BLOCK_NUM (insn));
  
  if (!see_store_reference_and_extension (ref_insn, insn,
                                          EXPLICIT_DEF_EXTENSION))
    /* Something bad happened.  Abort the optimization.  */
    return -1;

  return 0;
}

/* Go over all the uses, for each use in relevant web store its instruction as
   a reference and generate an extension before it.

   Return the number of relevant uses or negative number if something bad had
   happened and the optimization should be aborted.  */

static int
see_handle_relevant_uses (struct df_ref *ref, rtx insn)
{
  struct web_entry *root_entry = NULL;
  rtx se_insn = NULL;
  enum rtx_code extension_code;
  rtx reg = DF_REF_REAL_REG (ref);

  root_entry = unionfind_root (&use_entry[DF_REF_ID (ref)]);
  
  if (ENTRY_EI (root_entry)->relevancy != SIGN_EXTENDED_DEF
      && ENTRY_EI (root_entry)->relevancy != ZERO_EXTENDED_DEF)
    /* The current web is not relevant.  Continue to the next use.  */
    return 0;
  
  if (root_entry->reg)
    /* It isn't possible to have two different register for the same
       web.  */
    gcc_assert (rtx_equal_p (root_entry->reg, reg));
  else
    root_entry->reg = reg;
  
  /* Generate the use extension.  */
  if (ENTRY_EI (root_entry)->relevancy == SIGN_EXTENDED_DEF)
    extension_code = SIGN_EXTEND;
  else
    extension_code = ZERO_EXTEND;
  
  se_insn =
    see_gen_normalized_extension (reg, extension_code,
                                  ENTRY_EI (root_entry)->source_mode);
  if (!se_insn)
    /* This is very bad, abort the transformation.  */
    return -1;
  
  if (!see_store_reference_and_extension (insn, se_insn,
                                          USE_EXTENSION))
    /* Something bad happened.  Abort the optimization.  */
    return -1;
  return 1;
}

static int
see_handle_relevant_refs (void)
{
  int num_relevant_refs = 0;
  basic_block bb;

  FOR_ALL_BB (bb)
    {
      rtx insn;
      FOR_BB_INSNS (bb, insn)
        {
          unsigned int uid = INSN_UID (insn);

          if (INSN_P (insn))
            {
              struct df_ref **use_rec;
              struct df_ref **def_rec;
              
              for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
                {
                  struct df_ref *use = *use_rec;
                  int result = see_handle_relevant_uses (use, insn);
                  if (result == -1)
                    return -1;
                  num_relevant_refs += result;
                }
              for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
                {
                  struct df_ref *use = *use_rec;
                  int result = see_handle_relevant_uses (use, insn);
                  if (result == -1)
                    return -1;
                  num_relevant_refs += result;
                }
              for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
                {
                  struct df_ref *def = *def_rec;
                  int result = see_handle_relevant_defs (def, insn);
                  if (result == -1)
                    return -1;
                  num_relevant_refs += result;
                }
            }
        }
    }
   return num_relevant_refs;
}


/* Initialized the use_entry field for REF in INSN at INDEX with ET.  */

static void
see_update_uses_relevancy (rtx insn, struct df_ref *ref, 
                           enum entry_type et, unsigned int index)
{
  struct see_entry_extra_info *curr_entry_extra_info;

  if (dump_file)
    {
      rtx reg = DF_REF_REAL_REG (ref);
      fprintf (dump_file, "u%i insn %i reg %i ", 
               index, (insn ? INSN_UID (insn) : -1), REGNO (reg));
      if (et == NOT_RELEVANT)
        fprintf (dump_file, "NOT RELEVANT \n");
      else
        fprintf (dump_file, "RELEVANT USE \n");
    }

  DF_REF_ID (ref) = index;
  curr_entry_extra_info = xmalloc (sizeof (struct see_entry_extra_info));
  curr_entry_extra_info->relevancy = et;
  curr_entry_extra_info->local_relevancy = et;
  use_entry[index].extra_info = curr_entry_extra_info;
  use_entry[index].reg = NULL;
  use_entry[index].pred = NULL;
}


/* A definition in a candidate for this optimization only if its pattern is
   recognized as relevant in this function.
   INSN is the instruction to be recognized.

-  If this is the pattern of a common sign extension after definition:
   PREV_INSN (INSN):    def (reg:NARROWmode r)
   INSN:                set ((reg:WIDEmode r')
                             (sign_extend:WIDEmode (reg:NARROWmode r)))
   return SIGN_EXTENDED_DEF and set SOURCE_MODE to NARROWmode.

-  If this is the pattern of a common zero extension after definition:
   PREV_INSN (INSN):    def (reg:NARROWmode r)
   INSN:                set ((reg:WIDEmode r')
                             (zero_extend:WIDEmode (reg:NARROWmode r)))
   return ZERO_EXTENDED_DEF and set SOURCE_MODE to NARROWmode.

-  Otherwise,

   For the pattern:
   INSN:  set ((reg:WIDEmode r) (sign_extend:WIDEmode (...expr...)))
   return EXTENDED_DEF and set SOURCE_MODE to the mode of expr.

   For the pattern:
   INSN:  set ((reg:WIDEmode r) (zero_extend:WIDEmode (...expr...)))
   return EXTENDED_DEF and set SOURCE_MODE_UNSIGNED to the mode of expr.

   For the pattern:
   INSN:  set ((reg:WIDEmode r) (CONST_INT (...)))
   return EXTENDED_DEF and set SOURCE_MODE(_UNSIGNED) to the narrowest mode that
   is implicitly sign(zero) extended to WIDEmode in the INSN.

-  FIXME: Extensions that are not adjacent to their definition and EXTENDED_DEF
   that is part of a PARALLEL instruction are not handled.
   These restriction can be relaxed.  */

static enum entry_type
see_analyze_one_def (rtx insn, enum machine_mode *source_mode,
                     enum machine_mode *source_mode_unsigned)
{
  enum rtx_code extension_code;
  rtx rhs = NULL;
  rtx lhs = NULL;
  rtx set = NULL;
  rtx source_register = NULL;
  rtx prev_insn = NULL;
  rtx next_insn = NULL;
  enum machine_mode mode;
  enum machine_mode next_source_mode;
  HOST_WIDE_INT val = 0;
  HOST_WIDE_INT val2 = 0;
  int i = 0;

  *source_mode = MAX_MACHINE_MODE;
  *source_mode_unsigned = MAX_MACHINE_MODE;

  extension_code = see_get_extension_data (insn, source_mode);
  switch (extension_code)
    {
    case SIGN_EXTEND:
    case ZERO_EXTEND:
      source_register = see_get_extension_reg (insn, 0);
      /* FIXME: This restriction can be relaxed.  The only thing that is
         important is that the reference would be inside the same basic block
         as the extension.  */
      prev_insn = PREV_INSN (insn);
      if (!prev_insn || !INSN_P (prev_insn))
        return NOT_RELEVANT;

      if (!reg_set_between_p (source_register, PREV_INSN (prev_insn), insn))
        return NOT_RELEVANT;

      if (find_reg_note (prev_insn, REG_LIBCALL, NULL_RTX))
        return NOT_RELEVANT;

      if (find_reg_note (prev_insn, REG_RETVAL, NULL_RTX))
        return NOT_RELEVANT;

      /* If we can't use copy_rtx on the reference it can't be a reference.  */
      if (GET_CODE (PATTERN (prev_insn)) == PARALLEL
           && asm_noperands (PATTERN (prev_insn)) >= 0)
        return NOT_RELEVANT;

      /* Now, check if this extension is a reference itself.  If so, it is not
         relevant.  Handling this extension as relevant would make things much
         more complicated.  */
      next_insn = NEXT_INSN (insn);
      if (next_insn
          && INSN_P (next_insn)
          && (see_get_extension_data (next_insn, &next_source_mode) !=
              NOT_RELEVANT))
        {
          rtx curr_dest_register = see_get_extension_reg (insn, 1);
          rtx next_source_register = see_get_extension_reg (next_insn, 0);

          if (REGNO (curr_dest_register) == REGNO (next_source_register))
            return NOT_RELEVANT;
        }

      if (extension_code == SIGN_EXTEND)
        return SIGN_EXTENDED_DEF;
      else
        return ZERO_EXTENDED_DEF;

    case UNKNOWN:
      /* This may still be an EXTENDED_DEF.  */

      /* FIXME: This restriction can be relaxed.  It is possible to handle
         PARALLEL insns too.  */
      set = single_set (insn);
      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 NOT_RELEVANT;

      switch (GET_CODE (rhs))
        {
        case SIGN_EXTEND:
          *source_mode = GET_MODE (XEXP (rhs, 0));
          *source_mode_unsigned = MAX_MACHINE_MODE;
          return EXTENDED_DEF;
        case ZERO_EXTEND:
          *source_mode = MAX_MACHINE_MODE;
          *source_mode_unsigned = GET_MODE (XEXP (rhs, 0));
          return EXTENDED_DEF;
        case CONST_INT:

          val = INTVAL (rhs);

          /* Find the narrowest mode, val could fit into.  */
          for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT), i = 0;
               GET_MODE_BITSIZE (mode) < BITS_PER_WORD;
               mode = GET_MODE_WIDER_MODE (mode), i++)
            {
              val2 = trunc_int_for_mode (val, mode);
              if (val2 == val && *source_mode == MAX_MACHINE_MODE)
                *source_mode = mode;
              if (val == (val & (HOST_WIDE_INT)GET_MODE_MASK (mode))
                  && *source_mode_unsigned == MAX_MACHINE_MODE)
                *source_mode_unsigned = mode;
              if (*source_mode != MAX_MACHINE_MODE
                  && *source_mode_unsigned !=MAX_MACHINE_MODE)
                return EXTENDED_DEF;
            }
          if (*source_mode != MAX_MACHINE_MODE
              || *source_mode_unsigned !=MAX_MACHINE_MODE)
            return EXTENDED_DEF;
          return NOT_RELEVANT;
        default:
          return NOT_RELEVANT;
        }
    default:
      gcc_unreachable ();
    }
}


/* Initialized the def_entry field for REF in INSN at INDEX with ET.  */

static void
see_update_defs_relevancy (rtx insn, struct df_ref *ref,
                           enum entry_type et,
                           enum machine_mode source_mode,
                           enum machine_mode source_mode_unsigned,
                           unsigned int index)
{
  struct see_entry_extra_info *curr_entry_extra_info 
    = xmalloc (sizeof (struct see_entry_extra_info));
  curr_entry_extra_info->relevancy = et;
  curr_entry_extra_info->local_relevancy = et;

  DF_REF_ID (ref) = index;

  if (et != EXTENDED_DEF)
    {
      curr_entry_extra_info->source_mode = source_mode;
      curr_entry_extra_info->local_source_mode = source_mode;
    }
  else
    {
      curr_entry_extra_info->source_mode_signed = source_mode;
      curr_entry_extra_info->source_mode_unsigned = source_mode_unsigned;
    }
  def_entry[index].extra_info = curr_entry_extra_info;
  def_entry[index].reg = NULL;
  def_entry[index].pred = NULL;
  
  if (dump_file)
    {
      rtx reg = DF_REF_REAL_REG (ref);
      if (et == NOT_RELEVANT)
        {
          fprintf (dump_file, "d%i insn %i reg %i ",
                   index, (insn ? INSN_UID (insn) : -1), REGNO (reg));
          fprintf (dump_file, "NOT RELEVANT \n");
        }
      else
        {
          fprintf (dump_file, "d%i insn %i reg %i ",
                   index, INSN_UID (insn), REGNO (reg));
          fprintf (dump_file, "RELEVANT - ");
          switch (et)
            {
            case SIGN_EXTENDED_DEF :
              fprintf (dump_file, "SIGN_EXTENDED_DEF, source_mode = %s\n",
                       GET_MODE_NAME (source_mode));
              break;
            case ZERO_EXTENDED_DEF :
              fprintf (dump_file, "ZERO_EXTENDED_DEF, source_mode = %s\n",
                       GET_MODE_NAME (source_mode));
              break;
            case EXTENDED_DEF :
              fprintf (dump_file, "EXTENDED_DEF, ");
              if (source_mode != MAX_MACHINE_MODE
                  && source_mode_unsigned != MAX_MACHINE_MODE)
                {
                  fprintf (dump_file, "positive const, ");
                  fprintf (dump_file, "source_mode_signed = %s, ",
                           GET_MODE_NAME (source_mode));
                  fprintf (dump_file, "source_mode_unsigned = %s\n",
                           GET_MODE_NAME (source_mode_unsigned));
                }
              else if (source_mode != MAX_MACHINE_MODE)
                fprintf (dump_file, "source_mode_signed = %s\n",
                         GET_MODE_NAME (source_mode));
              else
                fprintf (dump_file, "source_mode_unsigned = %s\n",
                         GET_MODE_NAME (source_mode_unsigned));
              break;
            default :
              gcc_unreachable ();
            }
        }
    }
}


/* Updates the relevancy of all the uses and all defs.  

   The information of the u'th use is stored in use_entry[u] and the
   information of the d'th definition is stored in def_entry[d].

   Currently all the uses are relevant for the optimization except for
   uses that are in LIBCALL or RETVAL instructions.  */

static void
see_update_relevancy (void)
{
  unsigned int d = 0;
  unsigned int u = 0;
  enum entry_type et;
  enum machine_mode source_mode;
  enum machine_mode source_mode_unsigned;
  basic_block bb;

  if (!def_entry)
    return;

  FOR_ALL_BB (bb)
    {
      struct df_ref **use_rec;
      struct df_ref **def_rec;
      rtx insn;
      FOR_BB_INSNS (bb, insn)
        {
          unsigned int uid = INSN_UID (insn);
          if (INSN_P (insn))
            {
              if (find_reg_note (insn, REG_LIBCALL, NULL_RTX)
                  || find_reg_note (insn, REG_RETVAL, NULL_RTX))
                et = NOT_RELEVANT;
              else
                et = RELEVANT_USE;

              for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
                {
                  struct df_ref *use = *use_rec;
                  see_update_uses_relevancy (insn, use, et, u);
                  u++;
                }
              
              for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
                {
                  struct df_ref *use = *use_rec;
                  see_update_uses_relevancy (insn, use, et, u);
                  u++;
                }

              et = see_analyze_one_def (insn, &source_mode, &source_mode_unsigned);
              for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
                {
                  struct df_ref *def = *def_rec;
                  see_update_defs_relevancy (insn, def, et, source_mode, 
                                               source_mode_unsigned, d);
                  d++;
                }
            }
        }
      
      for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
        {
          struct df_ref *use = *use_rec;
          see_update_uses_relevancy (NULL, use, NOT_RELEVANT, u);
          u++;
        }

      for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
        {
          struct df_ref *def = *def_rec;
          see_update_defs_relevancy (NULL, def, NOT_RELEVANT, 
                                       MAX_MACHINE_MODE, MAX_MACHINE_MODE, d);
          d++;
        }
    }
}


/* Phase 1 top level function.
   In this phase the relevancy of all the definitions and uses are checked,
   later the webs are produces and the extensions are generated.
   These extensions are not emitted yet into the insns stream.

   returns true if at list one relevant web was found and there were no
   problems, otherwise return false.  */

static bool
see_propagate_extensions_to_uses (void)
{
  int num_relevant_refs;
  basic_block bb;

  if (dump_file)
    fprintf (dump_file,
      "* Phase 1: Propagate extensions to uses.  *\n");

  /* Update the relevancy of references using the DF object.  */
  see_update_relevancy ();

  /* Produce the webs and update the extra_info of the root.
     In general, a web is relevant if all its definitions and uses are relevant
     and there is at least one definition that was marked as SIGN_EXTENDED_DEF
     or ZERO_EXTENDED_DEF.  */
  FOR_ALL_BB (bb)
    {
      rtx insn;
      struct df_ref **use_rec;

      FOR_BB_INSNS (bb, insn)
        {
          unsigned int uid = INSN_UID (insn);
          if (INSN_P (insn))
            {
              for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
                {
                  struct df_ref *use = *use_rec;
                  union_defs (use, def_entry, use_entry, see_update_leader_extra_info);
                }
              
              for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
                {
                  struct df_ref *use = *use_rec;
                  union_defs (use, def_entry, use_entry, see_update_leader_extra_info);
                }
            }
        }

      for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
        {
          struct df_ref *use = *use_rec;
          union_defs (use, def_entry, use_entry, see_update_leader_extra_info);
        }
    }

  /* Generate use extensions for references and insert these
     references to see_bb_splay_ar data structure.    */
  num_relevant_refs = see_handle_relevant_refs ();

  return num_relevant_refs > 0;
}


/* Main entry point for the sign extension elimination optimization.  */

static void
see_main (void)
{
  bool cont = false;
  int i = 0;

  /* Initialize global data structures.  */
  see_initialize_data_structures ();

  /* Phase 1: Propagate extensions to uses.  */
  cont = see_propagate_extensions_to_uses ();

  if (cont)
    {
      init_recog ();

      /* Phase 2: Merge and eliminate locally redundant extensions.  */
      see_merge_and_eliminate_extensions ();

      /* Phase 3: Eliminate globally redundant extensions.  */
      see_execute_LCM ();

      /* Phase 4: Commit changes to the insn stream.  */
      see_commit_changes ();

      if (dump_file)
        {
          /* For debug purpose only.  */
          fprintf (dump_file, "see_pre_extension_hash:\n");
          htab_traverse (see_pre_extension_hash, see_print_pre_extension_expr,
                         NULL);

          for (i = 0; i < last_bb; i++)
            {
              if (see_bb_hash_ar[i])
                /* Traverse over all the references in the basic block in
                   forward order.  */
                {
                  fprintf (dump_file,
                           "Searching register properties in bb %d\n", i);
                  htab_traverse (see_bb_hash_ar[i],
                                 see_print_register_properties, NULL);
                }
            }
        }
    }

  /* Free global data structures.  */
  see_free_data_structures ();
}

\f
static bool
gate_handle_see (void)
{
  return optimize > 1 && flag_see;
}

static unsigned int
rest_of_handle_see (void)
{
  see_main ();
  df_clear_flags (DF_DEFER_INSN_RESCAN);
  df_process_deferred_rescans ();
  run_fast_dce ();
  return 0;
}

struct rtl_opt_pass pass_see =
{
 {
  RTL_PASS,
  "see",                                /* name */
  gate_handle_see,                      /* gate */
  rest_of_handle_see,                   /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_SEE,                               /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  TODO_df_verify |
  TODO_df_finish | TODO_verify_rtl_sharing |
  TODO_dump_func                        /* todo_flags_finish */
 }
};