Josef Zlomek <zlomekj@suse.cz>

	Josef Zlomek  <zlomekj@suse.cz>
	* Makefile.in (var-tracking.o): New.
	* common.opt (fvar-tracking): New.
	* flags.h (flag_var_tracking): New.
	* gengtype.c (adjust_field_rtx_def): NOTE_INSN_VAR_LOCATION was added.
	* opts.c (common_handle_option): Add OPT_fvar_tracking.
	* print-rtl.c (print_rtx): NOTE_INSN_VAR_LOCATION was added.
        * rtl.c (note_insn_name): Likewise.
        * rtl.def (VAR_LOCATION): New.
        * rtl.h (NOTE_VAR_LOCATION): New.
        (NOTE_VAR_LOCATION_DECL): New.
        (NOTE_VAR_LOCATION_LOC): New.
        (enum insn_note): NOTE_INSN_VAR_LOCATION was added.
        (variable_tracking_main): New exported function.
        * timevar.def (TV_VAR_TRACKING): New.
        * toplev.c (enum dump_file_index): Added DFI_vartrack.
        (dump_file): "vartrack" was added (-dV).
        (flag_var_tracking): New.
        (f_options): "var-tracking" was added.
	(rest_of_handle_variable_tracking): New function.
        (rest_of_compilation): Run variable tracking.
	(process_options): If user has not specified flag_var_tracking set it
	according to optimize, debug_info_level and debug_hooks.
	* tree.h (frame_base_decl): New.
        * var-tracking.c: New file.
	* config/ia64/ia64.c (ia64_flag_var_tracking): New variable.
	(ia64_override_options): Set flags to run variable tracking in machine
	dependent reorg instead of toplev.c.
	(ia64_reorg): Run variable tracking if wanted.
        * doc/invoke.texi: Mention variable tracking in -dV,
	add and -fvar-tracking.
        * doc/passes.texi: Added variable tracking pass.

	Daniel Berlin <dberlin@dberlin.org>
	* debug.h (struct gcc_debug_hooks): Added var_location debug hook.
	* dbxout.c (dbx_debug_hooks): Likewise.
	(xcoff_debug): Likewise.
	* debug.c (do_nothing_debug_hooks): Likewise.
	* dwarf2out.c (dwarf2_debug_hooks): Likewise.
	* dwarfout.c (dwarf_debug_hooks): Likewise.
	* sdbout.c (sdb_debug_hooks): Likewise.
	* vmsdbgout.c (vmsdbg_debug_hooks): Likewise.
	* final.c (final_scan_insn): Call var_location debug hook for each
	NOTE_INSN_VAR_LOCATION.

Co-Authored-By: Daniel Berlin <dberlin@dberlin.org>

From-SVN: r77418

1 files changed, 2633 insertions, 0 deletions

diff --git a/gcc/var-tracking.c b/gcc/var-tracking.c
new file mode 100644
index 0000000..7a1653d
--- /dev/null
+++ b/gcc/var-tracking.c
@@ -0,0 +1,2633 @@
+/* Variable tracking routines for the GNU compiler.
+   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+
+   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 2, 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 COPYING.  If not, write to the Free
+   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.  */
+
+/* This file contains the variable tracking pass.  It computes where
+   variables are located (which registers or where in memory) at each position
+   in instruction stream and emits notes describing the locations.
+   Debug information (DWARF2 location lists) is finally generated from
+   these notes.
+   With this debug information, it is possible to show variables
+   even when debugging optimized code.
+
+   How does the variable tracking pass work?
+
+   First, it scans RTL code for uses, stores and clobbers (register/memory
+   references in instructions), for call insns and for stack adjustments
+   separately for each basic block and saves them to an array of micro
+   operations.
+   The micro operations of one instruction are ordered so that
+   pre-modifying stack adjustment < use < use with no var < call insn <
+     < set < clobber < post-modifying stack adjustment
+
+   Then, a forward dataflow analysis is performed to find out how locations
+   of variables change through code and to propagate the variable locations
+   along control flow graph.
+   The IN set for basic block BB is computed as a union of OUT sets of BB's
+   predecessors, the OUT set for BB is copied from the IN set for BB and
+   is changed according to micro operations in BB.
+
+   The IN and OUT sets for basic blocks consist of a current stack adjustment
+   (used for adjusting offset of variables addressed using stack pointer),
+   the table of structures describing the locations of parts of a variable
+   and for each physical register a linked list for each physical register.
+   The linked list is a list of variable parts stored in the register,
+   i.e. it is a list of triplets (reg, decl, offset) where decl is
+   REG_EXPR (reg) and offset is REG_OFFSET (reg).  The linked list is used for
+   effective deleting appropriate variable parts when we set or clobber the
+   register.
+
+   There may be more than one variable part in a register.  The linked lists
+   should be pretty short so it is a good data structure here.
+   For example in the following code, register allocator may assign same
+   register to variables A and B, and both of them are stored in the same
+   register in CODE:
+
+     if (cond)
+       set A;
+     else
+       set B;
+     CODE;
+     if (cond)
+       use A;
+     else
+       use B;
+
+   Finally, the NOTE_INSN_VAR_LOCATION notes describing the variable locations
+   are emitted to appropriate positions in RTL code.  Each such a note describes
+   the location of one variable at the point in instruction stream where the
+   note is.  There is no need to emit a note for each variable before each
+   instruction, we only emit these notes where the location of variable changes
+   (this means that we also emit notes for changes between the OUT set of the
+   previous block and the IN set of the current block).
+
+   The notes consist of two parts:
+   1. the declaration (from REG_EXPR or MEM_EXPR)
+   2. the location of a variable - it is either a simple register/memory
+      reference (for simple variables, for example int),
+      or a parallel of register/memory references (for a large variables
+      which consist of several parts, for example long long).
+
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "tree.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "flags.h"
+#include "output.h"
+#include "insn-config.h"
+#include "reload.h"
+#include "sbitmap.h"
+#include "alloc-pool.h"
+#include "fibheap.h"
+#include "hashtab.h"
+
+/* Type of micro operation.  */
+enum micro_operation_type
+{
+  MO_USE,	/* Use location (REG or MEM).  */
+  MO_USE_NO_VAR,/* Use location which is not associated with a variable
+		   or the variable is not trackable.  */
+  MO_SET,	/* Set location.  */
+  MO_CLOBBER,	/* Clobber location.  */
+  MO_CALL,	/* Call insn.  */
+  MO_ADJUST	/* Adjust stack pointer. */
+};
+
+/* Where shall the note be emitted?  BEFORE or AFTER the instruction.  */
+enum emit_note_where
+{
+  EMIT_NOTE_BEFORE_INSN,
+  EMIT_NOTE_AFTER_INSN
+};
+
+/* Structure holding information about micro operation.  */
+typedef struct micro_operation_def
+{
+  /* Type of micro operation.  */
+  enum micro_operation_type type;
+
+  union {
+    /* Location.  */
+    rtx loc;
+
+    /* Stack adjustment.  */
+    HOST_WIDE_INT adjust;
+  } u;
+
+  /* The instruction which the micro operation is in.  */
+  rtx insn;
+} micro_operation;
+
+/* Structure for passing some other parameters to function
+   emit_note_insn_var_location.  */
+typedef struct emit_note_data_def
+{
+  /* The instruction which the note will be emitted before/after.  */
+  rtx insn;
+
+  /* Where the note will be emitted (before/after insn)?  */
+  enum emit_note_where where;
+} emit_note_data;
+
+/* Description of location of a part of a variable.  The content of a physical
+   register is described by a chain of these structures.
+   The chains are pretty short (usually 1 or 2 elements) and thus
+   chain is the best data structure.  */
+typedef struct attrs_def
+{
+  /* Pointer to next member of the list.  */
+  struct attrs_def *next;
+
+  /* The rtx of register.  */
+  rtx loc;
+
+  /* The declaration corresponding to LOC.  */
+  tree decl;
+
+  /* Offset from start of DECL.  */
+  HOST_WIDE_INT offset;
+} *attrs;
+
+/* Structure holding the IN or OUT set for a basic block.  */
+typedef struct dataflow_set_def
+{
+  /* Adjustment of stack offset.  */
+  HOST_WIDE_INT stack_adjust;
+
+  /* Attributes for registers (lists of attrs).  */
+  attrs regs[FIRST_PSEUDO_REGISTER];
+
+  /* Variable locations.  */
+  htab_t vars;
+} dataflow_set;
+
+/* The structure (one for each basic block) containing the information
+   needed for variable tracking.  */
+typedef struct variable_tracking_info_def
+{
+  /* Number of micro operations stored in the MOS array.  */
+  int n_mos;
+
+  /* The array of micro operations.  */
+  micro_operation *mos;
+
+  /* The IN and OUT set for dataflow analysis.  */
+  dataflow_set in;
+  dataflow_set out;
+
+  /* Has the block been visited in DFS?  */
+  bool visited;
+} *variable_tracking_info;
+
+/* Structure for chaining the locations.  */
+typedef struct location_chain_def
+{
+  /* Next element in the chain.  */
+  struct location_chain_def *next;
+
+  /* The location (REG or MEM).  */
+  rtx loc;
+} *location_chain;
+
+/* Structure describing one part of variable.  */
+typedef struct variable_part_def
+{
+  /* Chain of locations of the part.  */
+  location_chain loc_chain;
+
+  /* Location which was last emitted to location list.  */
+  rtx cur_loc;
+
+  /* The offset in the variable.  */
+  HOST_WIDE_INT offset;
+} variable_part;
+
+/* Maximum number of location parts.  */
+#define MAX_VAR_PARTS 16
+
+/* Structure describing where the variable is located.  */
+typedef struct variable_def
+{
+  /* The declaration of the variable.  */
+  tree decl;
+
+  /* Number of variable parts.  */
+  int n_var_parts;
+
+  /* The variable parts.  */
+  variable_part var_part[MAX_VAR_PARTS];
+} *variable;
+
+/* Hash function for DECL for VARIABLE_HTAB.  */
+#define VARIABLE_HASH_VAL(decl) ((size_t) (decl))
+
+/* Pointer to the BB's information specific to variable tracking pass.  */
+#define VTI(BB) ((variable_tracking_info) (BB)->aux)
+
+/* Alloc pool for struct attrs_def.  */
+static alloc_pool attrs_pool;
+
+/* Alloc pool for struct variable_def.  */
+static alloc_pool var_pool;
+
+/* Alloc pool for struct location_chain_def.  */
+static alloc_pool loc_chain_pool;
+
+/* Changed variables, notes will be emitted for them.  */
+static htab_t changed_variables;
+
+/* Shall notes be emitted?  */
+static bool emit_notes;
+
+/* Fake variable for stack pointer.  */
+tree frame_base_decl;
+
+/* Local function prototypes.  */
+static void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
+					  HOST_WIDE_INT *);
+static void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
+					       HOST_WIDE_INT *);
+static void bb_stack_adjust_offset (basic_block);
+static HOST_WIDE_INT prologue_stack_adjust (void);
+static bool vt_stack_adjustments (void);
+static rtx adjust_stack_reference (rtx, HOST_WIDE_INT);
+static hashval_t variable_htab_hash (const void *);
+static int variable_htab_eq (const void *, const void *);
+static void variable_htab_free (void *);
+
+static void init_attrs_list_set (attrs *);
+static void attrs_list_clear (attrs *);
+static attrs attrs_list_member (attrs, tree, HOST_WIDE_INT);
+static void attrs_list_insert (attrs *, tree, HOST_WIDE_INT, rtx);
+static void attrs_list_copy (attrs *, attrs);
+static void attrs_list_union (attrs *, attrs);
+
+static void vars_clear (htab_t);
+static int vars_copy_1 (void **, void *);
+static void vars_copy (htab_t, htab_t);
+static void var_reg_delete_and_set (dataflow_set *, rtx);
+static void var_reg_delete (dataflow_set *, rtx);
+static void var_regno_delete (dataflow_set *, int);
+static void var_mem_delete_and_set (dataflow_set *, rtx);
+static void var_mem_delete (dataflow_set *, rtx);
+
+static void dataflow_set_init (dataflow_set *, int);
+static void dataflow_set_clear (dataflow_set *);
+static void dataflow_set_copy (dataflow_set *, dataflow_set *);
+static int variable_union_info_cmp_pos (const void *, const void *);
+static int variable_union (void **, void *);
+static void dataflow_set_union (dataflow_set *, dataflow_set *);
+static bool variable_part_different_p (variable_part *, variable_part *);
+static bool variable_different_p (variable, variable);
+static int dataflow_set_different_1 (void **, void *);
+static int dataflow_set_different_2 (void **, void *);
+static bool dataflow_set_different (dataflow_set *, dataflow_set *);
+static void dataflow_set_destroy (dataflow_set *);
+
+static bool contains_symbol_ref (rtx);
+static bool track_expr_p (tree);
+static int count_uses (rtx *, void *);
+static void count_uses_1 (rtx *, void *);
+static void count_stores (rtx, rtx, void *);
+static int add_uses (rtx *, void *);
+static void add_uses_1 (rtx *, void *);
+static void add_stores (rtx, rtx, void *);
+static bool compute_bb_dataflow (basic_block);
+static void vt_find_locations (void);
+
+static void dump_attrs_list (attrs);
+static int dump_variable (void **, void *);
+static void dump_vars (htab_t);
+static void dump_dataflow_set (dataflow_set *);
+static void dump_dataflow_sets (void);
+
+static void variable_was_changed (variable, htab_t);
+static void set_frame_base_location (dataflow_set *, rtx);
+static void set_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT);
+static void delete_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT);
+static int emit_note_insn_var_location (void **, void *);
+static void emit_notes_for_changes (rtx, enum emit_note_where);
+static int emit_notes_for_differences_1 (void **, void *);
+static int emit_notes_for_differences_2 (void **, void *);
+static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
+static void emit_notes_in_bb (basic_block);
+static void vt_emit_notes (void);
+
+static bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *);
+static void vt_add_function_parameters (void);
+static void vt_initialize (void);
+static void vt_finalize (void);
+
+/* Given a SET, calculate the amount of stack adjustment it contains
+   PRE- and POST-modifying stack pointer.
+   This function is similar to stack_adjust_offset.  */
+
+static void
+stack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre,
+			      HOST_WIDE_INT *post)
+{
+  rtx src = SET_SRC (pattern);
+  rtx dest = SET_DEST (pattern);
+  enum rtx_code code;
+
+  if (dest == stack_pointer_rtx)
+    {
+      /* (set (reg sp) (plus (reg sp) (const_int))) */
+      code = GET_CODE (src);
+      if (! (code == PLUS || code == MINUS)
+	  || XEXP (src, 0) != stack_pointer_rtx
+	  || GET_CODE (XEXP (src, 1)) != CONST_INT)
+	return;
+
+      if (code == MINUS)
+	*post += INTVAL (XEXP (src, 1));
+      else
+	*post -= INTVAL (XEXP (src, 1));
+    }
+  else if (GET_CODE (dest) == MEM)
+    {
+      /* (set (mem (pre_dec (reg sp))) (foo)) */
+      src = XEXP (dest, 0);
+      code = GET_CODE (src);
+
+      switch (code)
+	{
+	case PRE_MODIFY:
+	case POST_MODIFY:
+	  if (XEXP (src, 0) == stack_pointer_rtx)
+	    {
+	      rtx val = XEXP (XEXP (src, 1), 1);
+	      /* We handle only adjustments by constant amount.  */
+	      if (GET_CODE (XEXP (src, 1)) != PLUS ||
+		  GET_CODE (val) != CONST_INT)
+		abort ();
+	      if (code == PRE_MODIFY)
+		*pre -= INTVAL (val);
+	      else
+		*post -= INTVAL (val);
+	      break;
+	    }
+	  return;
+
+	case PRE_DEC:
+	  if (XEXP (src, 0) == stack_pointer_rtx)
+	    {
+	      *pre += GET_MODE_SIZE (GET_MODE (dest));
+	      break;
+	    }
+	  return;
+
+	case POST_DEC:
+	  if (XEXP (src, 0) == stack_pointer_rtx)
+	    {
+	      *post += GET_MODE_SIZE (GET_MODE (dest));
+	      break;
+	    }
+	  return;
+
+	case PRE_INC:
+	  if (XEXP (src, 0) == stack_pointer_rtx)
+	    {
+	      *pre -= GET_MODE_SIZE (GET_MODE (dest));
+	      break;
+	    }
+	  return;
+
+	case POST_INC:
+	  if (XEXP (src, 0) == stack_pointer_rtx)
+	    {
+	      *post -= GET_MODE_SIZE (GET_MODE (dest));
+	      break;
+	    }
+	  return;
+
+	default:
+	  return;
+	}
+    }
+}
+
+/* Given an INSN, calculate the amount of stack adjustment it contains
+   PRE- and POST-modifying stack pointer.  */
+
+static void
+insn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre,
+				   HOST_WIDE_INT *post)
+{
+  *pre = 0;
+  *post = 0;
+
+  if (GET_CODE (PATTERN (insn)) == SET)
+    stack_adjust_offset_pre_post (PATTERN (insn), pre, post);
+  else if (GET_CODE (PATTERN (insn)) == PARALLEL
+	   || GET_CODE (PATTERN (insn)) == SEQUENCE)
+    {
+      int i;
+
+      /* There may be stack adjustments inside compound insns.  Search
+	 for them.  */
+      for ( i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+	if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
+	  stack_adjust_offset_pre_post (XVECEXP (PATTERN (insn), 0, i),
+					pre, post);
+    }
+}
+
+/* Compute stack adjustnment in basic block BB.  */
+
+static void
+bb_stack_adjust_offset (basic_block bb)
+{
+  HOST_WIDE_INT offset;
+  int i;
+
+  offset = VTI (bb)->in.stack_adjust;
+  for (i = 0; i < VTI (bb)->n_mos; i++)
+    {
+      if (VTI (bb)->mos[i].type == MO_ADJUST)
+	offset += VTI (bb)->mos[i].u.adjust;
+      else if (VTI (bb)->mos[i].type != MO_CALL)
+	{
+	  if (GET_CODE (VTI (bb)->mos[i].u.loc) == MEM)
+	    {
+	      VTI (bb)->mos[i].u.loc
+		= adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset);
+	    }
+	}
+    }
+  VTI (bb)->out.stack_adjust = offset;
+}
+
+/* Compute stack adjustment caused by function prolog.  */
+
+static HOST_WIDE_INT
+prologue_stack_adjust (void)
+{
+  HOST_WIDE_INT offset = 0;
+  basic_block bb = ENTRY_BLOCK_PTR->next_bb;
+  rtx insn;
+  rtx end;
+
+  if (!BB_END (bb))
+    return 0;
+
+  end = NEXT_INSN (BB_END (bb));
+  for (insn = BB_HEAD (bb); insn != end; insn = NEXT_INSN (insn))
+    {
+      if (GET_CODE (insn) == NOTE
+	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_PROLOGUE_END)
+	break;
+
+      if (INSN_P (insn))
+	{
+	  HOST_WIDE_INT tmp;
+
+	  insn_stack_adjust_offset_pre_post (insn, &tmp, &tmp);
+	  offset += tmp;
+	}
+    }
+
+  return offset;
+}
+
+/* Compute stack adjustments for all blocks by traversing DFS tree.
+   Return true when the adjustments on all incoming edges are consistent.
+   Heavily borrowed from flow_depth_first_order_compute.  */
+
+static bool
+vt_stack_adjustments (void)
+{
+  edge *stack;
+  int sp;
+
+  /* Initialize enttry block.  */
+  VTI (ENTRY_BLOCK_PTR)->visited = true;
+  VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = 0;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+  sp = 0;
+
+  /* Push the first edge on to the stack.  */
+  stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+  while (sp)
+    {
+      edge e;
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      e = stack[sp - 1];
+      src = e->src;
+      dest = e->dest;
+
+      /* Check if the edge destination has been visited yet.  */
+      if (!VTI (dest)->visited)
+	{
+	  VTI (dest)->visited = true;
+	  VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust;
+	  bb_stack_adjust_offset (dest);
+
+	  if (dest->succ)
+	    /* Since the DEST node has been visited for the first
+	       time, check its successors.  */
+	    stack[sp++] = dest->succ;
+	}
+      else
+	{
+	  /* Check whether the adjustments on the edges are the same.  */
+	  if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust)
+	    {
+	      free (stack);
+	      return false;
+	    }
+
+	  if (e->succ_next)
+	    /* Go to the next edge.  */
+	    stack[sp - 1] = e->succ_next;
+	  else
+	    /* Return to previous level if there are no more edges.  */
+	    sp--;
+	}
+    }
+
+  free (stack);
+  return true;
+}
+
+/* Adjust stack reference MEM by ADJUSTMENT bytes and return the new rtx.  */
+
+static rtx
+adjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment)
+{
+  rtx adjusted_mem;
+  rtx tmp;
+
+  adjusted_mem = copy_rtx (mem);
+  XEXP (adjusted_mem, 0) = replace_rtx (XEXP (adjusted_mem, 0),
+					stack_pointer_rtx,
+					gen_rtx_PLUS (Pmode, stack_pointer_rtx,
+						      GEN_INT (adjustment)));
+  tmp = simplify_rtx (XEXP (adjusted_mem, 0));
+  if (tmp)
+    XEXP (adjusted_mem, 0) = tmp;
+
+  return adjusted_mem;
+}
+
+/* The hash function for variable_htab, computes the hash value
+   from the declaration of variable X.  */
+
+static hashval_t
+variable_htab_hash (const void *x)
+{
+  const variable v = (const variable) x;
+
+  return (VARIABLE_HASH_VAL (v->decl));
+}
+
+/* Compare the declaration of variable X with declaration Y.  */
+
+static int
+variable_htab_eq (const void *x, const void *y)
+{
+  const variable v = (const variable) x;
+  const tree decl = (const tree) y;
+
+  return (VARIABLE_HASH_VAL (v->decl) == VARIABLE_HASH_VAL (decl));
+}
+
+/* Free the element of VARIABLE_HTAB (its type is struct variable_def).  */
+
+static void
+variable_htab_free (void *elem)
+{
+  int i;
+  variable var = (variable) elem;
+  location_chain node, next;
+
+  for (i = 0; i < var->n_var_parts; i++)
+    {
+      for (node = var->var_part[i].loc_chain; node; node = next)
+	{
+	  next = node->next;
+	  pool_free (loc_chain_pool, node);
+	}
+      var->var_part[i].loc_chain = NULL;
+    }
+  pool_free (var_pool, var);
+}
+
+/* Initialize the set (array) SET of attrs to empty lists.  */
+
+static void
+init_attrs_list_set (attrs *set)
+{
+  int i;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    set[i] = NULL;
+}
+
+/* Make the list *LISTP empty.  */
+
+static void
+attrs_list_clear (attrs *listp)
+{
+  attrs list, next;
+
+  for (list = *listp; list; list = next)
+    {
+      next = list->next;
+      pool_free (attrs_pool, list);
+    }
+  *listp = NULL;
+}
+
+/* Return true if the pair of DECL and OFFSET is the member of the LIST.  */
+
+static attrs
+attrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset)
+{
+  for (; list; list = list->next)
+    if (list->decl == decl && list->offset == offset)
+      return list;
+  return NULL;
+}
+
+/* Insert the triplet DECL, OFFSET, LOC to the list *LISTP.  */
+
+static void
+attrs_list_insert (attrs *listp, tree decl, HOST_WIDE_INT offset, rtx loc)
+{
+  attrs list;
+
+  list = pool_alloc (attrs_pool);
+  list->loc = loc;
+  list->decl = decl;
+  list->offset = offset;
+  list->next = *listp;
+  *listp = list;
+}
+
+/* Copy all nodes from SRC and create a list *DSTP of the copies.  */
+
+static void
+attrs_list_copy (attrs *dstp, attrs src)
+{
+  attrs n;
+
+  attrs_list_clear (dstp);
+  for (; src; src = src->next)
+    {
+      n = pool_alloc (attrs_pool);
+      n->loc = src->loc;
+      n->decl = src->decl;
+      n->offset = src->offset;
+      n->next = *dstp;
+      *dstp = n;
+    }
+}
+
+/* Add all nodes from SRC which are not in *DSTP to *DSTP.  */
+
+static void
+attrs_list_union (attrs *dstp, attrs src)
+{
+  for (; src; src = src->next)
+    {
+      if (!attrs_list_member (*dstp, src->decl, src->offset))
+	attrs_list_insert (dstp, src->decl, src->offset, src->loc);
+    }
+}
+
+/* Delete all variables from hash table VARS.  */
+
+static void
+vars_clear (htab_t vars)
+{
+  htab_empty (vars);
+}
+
+/* Copy one variable from *SLOT to hash table DATA.  */
+
+static int
+vars_copy_1 (void **slot, void *data)
+{
+  htab_t dst = (htab_t) data;
+  variable src, *dstp, var;
+  int i;
+
+  src = *(variable *) slot;
+  dstp = (variable *) htab_find_slot_with_hash (dst, src->decl,
+						VARIABLE_HASH_VAL (src->decl),
+						INSERT);
+  var = pool_alloc (var_pool);
+  var->decl = src->decl;
+  var->n_var_parts = src->n_var_parts;
+  *dstp = (void *) var;
+
+  for (i = 0; i < var->n_var_parts; i++)
+    {
+      location_chain last, node;
+
+      var->var_part[i].offset = src->var_part[i].offset;
+      last = NULL;
+      for (node = src->var_part[i].loc_chain; node; node = node->next)
+	{
+	  location_chain new_lc;
+
+	  new_lc = pool_alloc (loc_chain_pool);
+	  new_lc->next = NULL;
+	  new_lc->loc = node->loc;
+
+	  if (last)
+	    last->next = new_lc;
+	  else
+	    var->var_part[i].loc_chain = new_lc;
+	  last = new_lc;
+	}
+
+      /* We are at the basic block boundary when copying variable description
+	 so set the CUR_LOC to be the first element of the chain.  */
+      if (var->var_part[i].loc_chain)
+	var->var_part[i].cur_loc = var->var_part[i].loc_chain->loc;
+      else
+	var->var_part[i].cur_loc = NULL;
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Copy all variables from hash table SRC to hash table DST.  */
+
+static void
+vars_copy (htab_t dst, htab_t src)
+{
+  vars_clear (dst);
+  htab_traverse (src, vars_copy_1, dst);
+}
+
+/* Delete current content of register LOC in dataflow set SET
+   and set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  */
+
+static void
+var_reg_delete_and_set (dataflow_set *set, rtx loc)
+{
+  attrs *reg = &set->regs[REGNO (loc)];
+  tree decl = REG_EXPR (loc);
+  HOST_WIDE_INT offset = REG_OFFSET (loc);
+  attrs node, prev, next;
+
+  prev = NULL;
+  for (node = *reg; node; node = next)
+    {
+      next = node->next;
+      if (node->decl != decl || node->offset != offset)
+	{
+	  delete_variable_part (set, node->loc, node->decl, node->offset);
+
+	  if (prev)
+	    prev->next = next;
+	  else
+	    *reg = next;
+	  pool_free (attrs_pool, node);
+	}
+      else
+	{
+	  node->loc = loc;
+	  prev = node;
+	}
+    }
+  if (*reg == NULL)
+    attrs_list_insert (reg, decl, offset, loc);
+  set_variable_part (set, loc, decl, offset);
+}
+
+/* Delete current content of register LOC in dataflow set SET.  */
+
+static void
+var_reg_delete (dataflow_set *set, rtx loc)
+{
+  attrs *reg = &set->regs[REGNO (loc)];
+  attrs node, next;
+
+  for (node = *reg; node; node = next)
+    {
+      next = node->next;
+      delete_variable_part (set, node->loc, node->decl, node->offset);
+      pool_free (attrs_pool, node);
+    }
+  *reg = NULL;
+}
+
+/* Delete content of register with number REGNO in dataflow set SET.  */
+
+static void
+var_regno_delete (dataflow_set *set, int regno)
+{
+  attrs *reg = &set->regs[regno];
+  attrs node, next;
+
+  for (node = *reg; node; node = next)
+    {
+      next = node->next;
+      delete_variable_part (set, node->loc, node->decl, node->offset);
+      pool_free (attrs_pool, node);
+    }
+  *reg = NULL;
+}
+
+/* Delete and set the location part of variable MEM_EXPR (LOC)
+   in dataflow set SET to LOC.
+   Adjust the address first if it is stack pointer based.  */
+
+static void
+var_mem_delete_and_set (dataflow_set *set, rtx loc)
+{
+  tree decl = MEM_EXPR (loc);
+  HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0;
+
+  set_variable_part (set, loc, decl, offset);
+}
+
+/* Delete the location part LOC from dataflow set SET.
+   Adjust the address first if it is stack pointer based.  */
+
+static void
+var_mem_delete (dataflow_set *set, rtx loc)
+{
+  tree decl = MEM_EXPR (loc);
+  HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0;
+
+  delete_variable_part (set, loc, decl, offset);
+}
+
+/* Initialize dataflow set SET to be empty. 
+   VARS_SIZE is the initial size of hash table VARS.  */
+
+static void
+dataflow_set_init (dataflow_set *set, int vars_size)
+{
+  init_attrs_list_set (set->regs);
+  set->vars = htab_create (vars_size, variable_htab_hash, variable_htab_eq,
+			   variable_htab_free);
+  set->stack_adjust = 0;
+}
+
+/* Delete the contents of dataflow set SET.  */
+
+static void
+dataflow_set_clear (dataflow_set *set)
+{
+  int i;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    attrs_list_clear (&set->regs[i]);
+
+  vars_clear (set->vars);
+}
+
+/* Copy the contents of dataflow set SRC to DST.  */
+
+static void
+dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
+{
+  int i;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    attrs_list_copy (&dst->regs[i], src->regs[i]);
+
+  vars_copy (dst->vars, src->vars);
+  dst->stack_adjust = src->stack_adjust;
+}
+
+/* Information for merging lists of locations for a given offset of variable.
+ */
+struct variable_union_info
+{
+  /* Node of the location chain.  */
+  location_chain lc;
+
+  /* The sum of positions in the input chains.  */
+  int pos;
+
+  /* The position in the chains of SRC and DST dataflow sets.  */
+  int pos_src;
+  int pos_dst;
+};
+
+/* Compare function for qsort, order the structures by POS element.  */
+
+static int
+variable_union_info_cmp_pos (const void *n1, const void *n2)
+{
+  const struct variable_union_info *i1 = n1;
+  const struct variable_union_info *i2 = n2;
+
+  if (i1->pos != i2->pos)
+    return i1->pos - i2->pos;
+  
+  return (i1->pos_dst - i2->pos_dst);
+}
+
+/* Compute union of location parts of variable *SLOT and the same variable
+   from hash table DATA.  Compute "sorted" union of the location chains
+   for common offsets, i.e. the locations of a variable part are sorted by
+   a priority where the priority is the sum of the positions in the 2 chains
+   (if a location is only in one list the position in the second list is
+   defined to be larger than the length of the chains).
+   When we are updating the location parts the newest location is in the
+   beginning of the chain, so when we do the described "sorted" union
+   we keep the newest locations in the beginning.  */
+
+static int
+variable_union (void **slot, void *data)
+{
+  variable src, dst, *dstp;
+  dataflow_set *set = (dataflow_set *) data;
+  int i, j, k;
+
+  src = *(variable *) slot;
+  dstp = (variable *) htab_find_slot_with_hash (set->vars, src->decl,
+						VARIABLE_HASH_VAL (src->decl),
+						INSERT);
+  if (!*dstp)
+    {
+      *dstp = dst = pool_alloc (var_pool);
+      dst->decl = src->decl;
+      dst->n_var_parts = 0;
+    }
+  else
+    dst = *dstp;
+
+#ifdef ENABLE_CHECKING
+  if (src->n_var_parts == 0)
+    abort ();
+#endif
+
+  /* Count the number of location parts, result is K.  */
+  for (i = 0, j = 0, k = 0;
+       i < src->n_var_parts && j < dst->n_var_parts; k++)
+    {
+      if (src->var_part[i].offset == dst->var_part[j].offset)
+	{
+	  i++;
+	  j++;
+	}
+      else if (src->var_part[i].offset < dst->var_part[j].offset)
+	i++;
+      else
+	j++;
+    }
+  if (i < src->n_var_parts)
+    k += src->n_var_parts - i;
+  if (j < dst->n_var_parts)
+    k += dst->n_var_parts - j;
+#ifdef ENABLE_CHECKING
+  /* We track only variables whose size is <= MAX_VAR_PARTS bytes
+     thus there are at most MAX_VAR_PARTS different offsets.  */
+  if (k > MAX_VAR_PARTS)
+    abort ();
+#endif
+
+  i = src->n_var_parts - 1;
+  j = dst->n_var_parts - 1;
+  dst->n_var_parts = k;
+
+  for (k--; k >= 0; k--)
+    {
+      location_chain node;
+
+      if (i >= 0 && j >= 0
+	  && src->var_part[i].offset == dst->var_part[j].offset)
+	{
+	  /* Compute the "sorted" union of the chains, i.e. the locations which
+	     are in both chains go first, they are sorted by the sum of
+	     positions in the chains.  */
+	  int dst_l, src_l;
+	  int ii, jj, n;
+	  struct variable_union_info *vui;
+	  
+	  src_l = 0;
+	  for (node = src->var_part[i].loc_chain; node; node = node->next)
+	    src_l++;
+	  dst_l = 0;
+	  for (node = dst->var_part[j].loc_chain; node; node = node->next)
+	    dst_l++;
+	  vui = xcalloc (src_l + dst_l, sizeof (struct variable_union_info));
+
+	  /* Fill in the locations from DST.  */
+	  for (node = dst->var_part[j].loc_chain, jj = 0; node;
+	       node = node->next, jj++)
+	    {
+	      vui[jj].lc = node;
+	      vui[jj].pos_dst = jj;
+
+	      /* Value larger than a sum of 2 valid positions.  */
+	      vui[jj].pos_src = src_l + dst_l;
+	    }
+
+	  /* Fill in the locations from SRC.  */
+	  n = dst_l;
+	  for (node = src->var_part[i].loc_chain, ii = 0; node;
+	       node = node->next, ii++)
+	    {
+	      /* Find location from NODE.  */
+	      for (jj = 0; jj < dst_l; jj++)
+		{
+		  if ((GET_CODE (vui[jj].lc->loc) == REG
+		       && GET_CODE (node->loc) == REG
+		       && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
+		      || rtx_equal_p (vui[jj].lc->loc, node->loc))
+		    {
+		      vui[jj].pos_src = ii;
+		      break;
+		    }
+		}
+	      if (jj >= dst_l)	/* The location has not been found.  */
+		{
+		  location_chain new_node;
+
+		  /* Copy the location from SRC.  */
+		  new_node = pool_alloc (loc_chain_pool);
+		  new_node->loc = node->loc;
+		  vui[n].lc = new_node;
+		  vui[n].pos_src = ii;
+		  vui[n].pos_dst = src_l + dst_l;
+		  n++;
+		}
+	    }
+
+	  for (ii = 0; ii < src_l + dst_l; ii++)
+	    vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst;
+
+	  qsort (vui, n, sizeof (struct variable_union_info),
+		 variable_union_info_cmp_pos);
+
+	  /* Reconnect the nodes in sorted order.  */
+	  for (ii = 1; ii < n; ii++)
+	    vui[ii - 1].lc->next = vui[ii].lc;
+	  vui[n - 1].lc->next = NULL;
+
+	  dst->var_part[k].loc_chain = vui[0].lc;
+	  dst->var_part[k].offset = dst->var_part[j].offset;
+
+	  free (vui);
+	  i--;
+	  j--;
+	}
+      else if ((i >= 0 && j >= 0
+		&& src->var_part[i].offset < dst->var_part[j].offset)
+	       || i < 0)
+	{
+	  dst->var_part[k] = dst->var_part[j];
+	  j--;
+	}
+      else if ((i >= 0 && j >= 0
+		&& src->var_part[i].offset > dst->var_part[j].offset)
+	       || j < 0)
+	{
+	  location_chain last = NULL;
+
+	  /* Copy the chain from SRC.  */
+	  for (node = src->var_part[i].loc_chain; node; node = node->next)
+	    {
+	      location_chain new_lc;
+
+	      new_lc = pool_alloc (loc_chain_pool);
+	      new_lc->next = NULL;
+	      new_lc->loc = node->loc;
+
+	      if (last)
+		last->next = new_lc;
+	      else
+		dst->var_part[k].loc_chain = new_lc;
+	      last = new_lc;
+	    }
+
+	  dst->var_part[k].offset = src->var_part[i].offset;
+	  i--;
+	}
+
+      /* We are at the basic block boundary when computing union
+	 so set the CUR_LOC to be the first element of the chain.  */
+      if (dst->var_part[k].loc_chain)
+	dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
+      else
+	dst->var_part[k].cur_loc = NULL;
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Compute union of dataflow sets SRC and DST and store it to DST.  */
+
+static void
+dataflow_set_union (dataflow_set *dst, dataflow_set *src)
+{
+  int i;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    attrs_list_union (&dst->regs[i], src->regs[i]);
+
+  htab_traverse (src->vars, variable_union, dst);
+}
+
+/* Flag whether two dataflow sets being compared contain different data.  */
+static bool
+dataflow_set_different_value;
+
+static bool
+variable_part_different_p (variable_part *vp1, variable_part *vp2)
+{
+  location_chain lc1, lc2;
+
+  for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
+    {
+      for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
+	{
+	  if (GET_CODE (lc1->loc) == REG && GET_CODE (lc2->loc) == REG)
+	    {
+	      if (REGNO (lc1->loc) == REGNO (lc2->loc))
+		break;
+	    }
+	  if (rtx_equal_p (lc1->loc, lc2->loc))
+	    break;
+	}
+      if (!lc2)
+	return true;
+    }
+  return false;
+}
+
+/* Return true if variables VAR1 and VAR2 are different (only the first
+   location in the list of locations is checked for each offset,
+   i.e. when true is returned a note should be emitted).  */
+
+static bool
+variable_different_p (variable var1, variable var2)
+{
+  int i;
+
+  if (var1->n_var_parts != var2->n_var_parts)
+    return true;
+
+  for (i = 0; i < var1->n_var_parts; i++)
+    {
+      if (var1->var_part[i].offset != var2->var_part[i].offset)
+	return true;
+      if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
+	return true;
+      if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
+	return true;
+    }
+  return false;
+}
+
+/* Compare variable *SLOT with the same variable in hash table DATA
+   and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
+
+static int
+dataflow_set_different_1 (void **slot, void *data)
+{
+  htab_t htab = (htab_t) data;
+  variable var1, var2;
+
+  var1 = *(variable *) slot;
+  var2 = (variable) htab_find_with_hash (htab, var1->decl,
+					 VARIABLE_HASH_VAL (var1->decl));
+  if (!var2)
+    {
+      dataflow_set_different_value = true;
+
+      /* Stop traversing the hash table.   */
+      return 0;
+    }
+
+  if (variable_different_p (var1, var2))
+    {
+      dataflow_set_different_value = true;
+
+      /* Stop traversing the hash table.   */
+      return 0;
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Compare variable *SLOT with the same variable in hash table DATA
+   and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
+
+static int
+dataflow_set_different_2 (void **slot, void *data)
+{
+  htab_t htab = (htab_t) data;
+  variable var1, var2;
+
+  var1 = *(variable *) slot;
+  var2 = (variable) htab_find_with_hash (htab, var1->decl,
+					 VARIABLE_HASH_VAL (var1->decl));
+  if (!var2)
+    {
+      dataflow_set_different_value = true;
+
+      /* Stop traversing the hash table.   */
+      return 0;
+    }
+
+#ifdef ENABLE_CHECKING
+  /* If both variables are defined they have been already checked for
+     equivalence.  */
+  if (variable_different_p (var1, var2))
+    abort ();
+#endif
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Return true if dataflow sets OLD_SET and NEW_SET differ.  */
+
+static bool
+dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
+{
+  dataflow_set_different_value = false;
+
+  htab_traverse (old_set->vars, dataflow_set_different_1, new_set->vars);
+  if (!dataflow_set_different_value)
+    {
+      /* We have compared the variables which are in both hash tables
+	 so now only check whether there are some variables in NEW_SET->VARS
+	 which are not in OLD_SET->VARS.  */
+      htab_traverse (new_set->vars, dataflow_set_different_2, old_set->vars);
+    }
+  return dataflow_set_different_value;
+}
+
+/* Free the contents of dataflow set SET.  */
+
+static void
+dataflow_set_destroy (dataflow_set *set)
+{
+  int i;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    attrs_list_clear (&set->regs[i]);
+
+  htab_delete (set->vars);
+  set->vars = NULL;
+}
+
+/* Return true if RTL X contains a SYMBOL_REF.  */
+
+static bool
+contains_symbol_ref (rtx x)
+{
+  const char *fmt;
+  RTX_CODE code;
+  int i;
+
+  if (!x)
+    return false;
+
+  code = GET_CODE (x);
+  if (code == SYMBOL_REF)
+    return true;
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  if (contains_symbol_ref (XEXP (x, i)))
+	    return true;
+	}
+      else if (fmt[i] == 'E')
+	{
+	  int j;
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    if (contains_symbol_ref (XVECEXP (x, i, j)))
+	      return true;
+	}
+    }
+
+  return false;
+}
+
+/* Shall EXPR be tracked?  */
+
+static bool
+track_expr_p (tree expr)
+{
+  rtx decl_rtl;
+
+  /* If EXPR is not a parameter or a variable do not track it.  */
+  if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
+    return 0;
+
+  /* It also must have a name...  */
+  if (!DECL_NAME (expr))
+    return 0;
+
+  /* ... and a RTL assigned to it.  */
+  decl_rtl = DECL_RTL_IF_SET (expr);
+  if (!decl_rtl)
+    return 0;
+
+  /* Do not track global variables until we are able to emit correct location
+     list for them.  */
+  if (TREE_STATIC (expr))
+    return 0;
+
+  /* When the EXPR is a DECL for alias of some variable (see example)
+     the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
+     DECL_RTL contains SYMBOL_REF.
+
+     Example:
+     extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
+     char **_dl_argv;
+  */
+  if (GET_CODE (decl_rtl) == MEM
+      && contains_symbol_ref (XEXP (decl_rtl, 0)))
+    return 0;
+
+  /* If RTX is a memory it should not be very large (because it would be
+     an array or struct).  */
+  if (GET_CODE (decl_rtl) == MEM)
+    {
+      /* Do not track structures and arrays.  */
+      if (GET_MODE (decl_rtl) == BLKmode)
+	return 0;
+      if (MEM_SIZE (decl_rtl)
+	  && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
+	return 0;
+    }
+
+  return 1;
+}
+
+/* Count uses (register and memory references) LOC which will be tracked.
+   INSN is instruction which the LOC is part of.  */
+
+static int
+count_uses (rtx *loc, void *insn)
+{
+  basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
+
+  if (GET_CODE (*loc) == REG)
+    {
+#ifdef ENABLE_CHECKING
+	if (REGNO (*loc) >= FIRST_PSEUDO_REGISTER)
+	  abort ();
+#endif
+	VTI (bb)->n_mos++;
+    }
+  else if (GET_CODE (*loc) == MEM
+	   && MEM_EXPR (*loc)
+	   && track_expr_p (MEM_EXPR (*loc)))
+    {
+	  VTI (bb)->n_mos++;
+    }
+
+  return 0;
+}
+
+/* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
+
+static void
+count_uses_1 (rtx *x, void *insn)
+{
+  for_each_rtx (x, count_uses, insn);
+}
+
+/* Count stores (register and memory references) LOC which will be tracked.
+   INSN is instruction which the LOC is part of.  */
+
+static void
+count_stores (rtx loc, rtx expr ATTRIBUTE_UNUSED, void *insn)
+{
+  count_uses (&loc, insn);
+}
+
+/* Add uses (register and memory references) LOC which will be tracked
+   to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
+
+static int
+add_uses (rtx *loc, void *insn)
+{
+  if (GET_CODE (*loc) == REG)
+    {
+      basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
+      micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+      mo->type = ((REG_EXPR (*loc) && track_expr_p (REG_EXPR (*loc)))
+		  ? MO_USE : MO_USE_NO_VAR);
+      mo->u.loc = *loc;
+      mo->insn = (rtx) insn;
+    }
+  else if (GET_CODE (*loc) == MEM
+	   && MEM_EXPR (*loc)
+	   && track_expr_p (MEM_EXPR (*loc)))
+    {
+      basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
+      micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+      mo->type = MO_USE;
+      mo->u.loc = *loc;
+      mo->insn = (rtx) insn;
+    }
+
+  return 0;
+}
+
+/* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
+
+static void
+add_uses_1 (rtx *x, void *insn)
+{
+  for_each_rtx (x, add_uses, insn);
+}
+
+/* Add stores (register and memory references) LOC which will be tracked
+   to VTI (bb)->mos. EXPR is the RTL expression containing the store.
+   INSN is instruction which the LOC is part of.  */
+
+static void
+add_stores (rtx loc, rtx expr, void *insn)
+{
+  if (GET_CODE (loc) == REG)
+    {
+      basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
+      micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+      mo->type = ((GET_CODE (expr) != CLOBBER && REG_EXPR (loc)
+		   && track_expr_p (REG_EXPR (loc)))
+		  ? MO_SET : MO_CLOBBER);
+      mo->u.loc = loc;
+      mo->insn = (rtx) insn;
+    }
+  else if (GET_CODE (loc) == MEM
+	   && MEM_EXPR (loc)
+	   && track_expr_p (MEM_EXPR (loc)))
+    {
+      basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
+      micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+      mo->type = GET_CODE (expr) == CLOBBER ? MO_CLOBBER : MO_SET;
+      mo->u.loc = loc;
+      mo->insn = (rtx) insn;
+    }
+}
+
+/* Compute the changes of variable locations in the basic block BB.  */
+
+static bool
+compute_bb_dataflow (basic_block bb)
+{
+  int i, n, r;
+  bool changed;
+  dataflow_set old_out;
+  dataflow_set *in = &VTI (bb)->in;
+  dataflow_set *out = &VTI (bb)->out;
+
+  dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3);
+  dataflow_set_copy (&old_out, out);
+  dataflow_set_copy (out, in);
+
+  n = VTI (bb)->n_mos;
+  for (i = 0; i < n; i++)
+    {
+      switch (VTI (bb)->mos[i].type)
+	{
+	  case MO_CALL:
+	    for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
+	      if (TEST_HARD_REG_BIT (call_used_reg_set, r))
+		var_regno_delete (out, r);
+	    break;
+
+	  case MO_USE:
+	  case MO_SET:
+	    {
+	      rtx loc = VTI (bb)->mos[i].u.loc;
+
+	      if (GET_CODE (loc) == REG)
+		var_reg_delete_and_set (out, loc);
+	      else if (GET_CODE (loc) == MEM)
+		var_mem_delete_and_set (out, loc);
+	    }
+	    break;
+
+	  case MO_USE_NO_VAR:
+	  case MO_CLOBBER:
+	    {
+	      rtx loc = VTI (bb)->mos[i].u.loc;
+
+	      if (GET_CODE (loc) == REG)
+		var_reg_delete (out, loc);
+	      else if (GET_CODE (loc) == MEM)
+		var_mem_delete (out, loc);
+	    }
+	    break;
+
+	  case MO_ADJUST:
+	    {
+	      rtx base;
+
+	      out->stack_adjust += VTI (bb)->mos[i].u.adjust;
+	      base = gen_rtx_MEM (Pmode,
+				  gen_rtx_PLUS (Pmode, stack_pointer_rtx,
+						GEN_INT (out->stack_adjust)));
+	      set_frame_base_location (out, base);
+	    }
+	    break;
+	}
+    }
+
+  changed = dataflow_set_different (&old_out, out);
+  dataflow_set_destroy (&old_out);
+  return changed;
+}
+
+/* Find the locations of variables in the whole function.  */
+
+static void
+vt_find_locations (void)
+{
+  fibheap_t worklist, pending, fibheap_swap;
+  sbitmap visited, in_worklist, in_pending, sbitmap_swap;
+  basic_block bb;
+  edge e;
+  int *bb_order;
+  int *rc_order;
+  int i;
+
+  /* Compute reverse completion order of depth first search of the CFG
+     so that the data-flow runs faster.  */
+  rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
+  bb_order = (int *) xmalloc (last_basic_block * sizeof (int));
+  flow_depth_first_order_compute (NULL, rc_order);
+  for (i = 0; i < n_basic_blocks; i++)
+    bb_order[rc_order[i]] = i;
+  free (rc_order);
+
+  worklist = fibheap_new ();
+  pending = fibheap_new ();
+  visited = sbitmap_alloc (last_basic_block);
+  in_worklist = sbitmap_alloc (last_basic_block);
+  in_pending = sbitmap_alloc (last_basic_block);
+  sbitmap_zero (in_worklist);
+  sbitmap_zero (in_pending);
+
+  FOR_EACH_BB (bb)
+    {
+      fibheap_insert (pending, bb_order[bb->index], bb);
+      SET_BIT (in_pending, bb->index);
+    }
+
+  while (!fibheap_empty (pending))
+    {
+      fibheap_swap = pending;
+      pending = worklist;
+      worklist = fibheap_swap;
+      sbitmap_swap = in_pending;
+      in_pending = in_worklist;
+      in_worklist = sbitmap_swap;
+
+      sbitmap_zero (visited);
+
+      while (!fibheap_empty (worklist))
+	{
+	  bb = fibheap_extract_min (worklist);
+	  RESET_BIT (in_worklist, bb->index);
+	  if (!TEST_BIT (visited, bb->index))
+	    {
+	      bool changed;
+
+	      SET_BIT (visited, bb->index);
+
+	      /* Calculate the IN set as union of predecessor OUT sets.  */
+	      dataflow_set_clear (&VTI (bb)->in);
+	      for (e = bb->pred; e; e = e->pred_next)
+		{
+		  dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
+		}
+
+	      changed = compute_bb_dataflow (bb);
+	      if (changed)
+		{
+		  for (e = bb->succ; e; e = e->succ_next)
+		    {
+		      if (e->dest == EXIT_BLOCK_PTR)
+			continue;
+
+		      if (e->dest == bb)
+			continue;
+
+		      if (TEST_BIT (visited, e->dest->index))
+			{
+			  if (!TEST_BIT (in_pending, e->dest->index))
+			    {
+			      /* Send E->DEST to next round.  */
+			      SET_BIT (in_pending, e->dest->index);
+			      fibheap_insert (pending,
+					      bb_order[e->dest->index],
+					      e->dest);
+			    }
+			}
+		      else if (!TEST_BIT (in_worklist, e->dest->index))
+			{
+			  /* Add E->DEST to current round.  */
+			  SET_BIT (in_worklist, e->dest->index);
+			  fibheap_insert (worklist, bb_order[e->dest->index],
+					  e->dest);
+			}
+		    }
+		}
+	    }
+	}
+    }
+
+  free (bb_order);
+  fibheap_delete (worklist);
+  fibheap_delete (pending);
+  sbitmap_free (visited);
+  sbitmap_free (in_worklist);
+  sbitmap_free (in_pending);
+}
+
+/* Print the content of the LIST to dump file.  */
+
+static void
+dump_attrs_list (attrs list)
+{
+  for (; list; list = list->next)
+    {
+      print_mem_expr (rtl_dump_file, list->decl);
+      fprintf (rtl_dump_file, "+");
+      fprintf (rtl_dump_file, HOST_WIDE_INT_PRINT_DEC, list->offset);
+    }
+  fprintf (rtl_dump_file, "\n");
+}
+
+/* Print the information about variable *SLOT to dump file.  */
+
+static int
+dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  variable var = *(variable *) slot;
+  int i;
+  location_chain node;
+
+  fprintf (rtl_dump_file, "  name: %s\n",
+	   IDENTIFIER_POINTER (DECL_NAME (var->decl)));
+  for (i = 0; i < var->n_var_parts; i++)
+    {
+      fprintf (rtl_dump_file, "    offset %ld\n",
+	       (long) var->var_part[i].offset);
+      for (node = var->var_part[i].loc_chain; node; node = node->next)
+	{
+	  fprintf (rtl_dump_file, "      ");
+	  print_rtl_single (rtl_dump_file, node->loc);
+	}
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Print the information about variables from hash table VARS to dump file.  */
+
+static void
+dump_vars (htab_t vars)
+{
+  if (htab_elements (vars) > 0)
+    {
+      fprintf (rtl_dump_file, "Variables:\n");
+      htab_traverse (vars, dump_variable, NULL);
+    }
+}
+
+/* Print the dataflow set SET to dump file.  */
+
+static void
+dump_dataflow_set (dataflow_set *set)
+{
+  int i;
+
+  fprintf (rtl_dump_file, "Stack adjustment: ");
+  fprintf (rtl_dump_file, HOST_WIDE_INT_PRINT_DEC, set->stack_adjust);
+  fprintf (rtl_dump_file, "\n");
+  for (i = 1; i < FIRST_PSEUDO_REGISTER; i++)
+    {
+      if (set->regs[i])
+	{
+	  fprintf (rtl_dump_file, "Reg %d:", i);
+	  dump_attrs_list (set->regs[i]);
+	}
+    }
+  dump_vars (set->vars);
+  fprintf (rtl_dump_file, "\n");
+}
+
+/* Print the IN and OUT sets for each basic block to dump file.  */
+
+static void
+dump_dataflow_sets (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB (bb)
+    {
+      fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index);
+      fprintf (rtl_dump_file, "IN:\n");
+      dump_dataflow_set (&VTI (bb)->in);
+      fprintf (rtl_dump_file, "OUT:\n");
+      dump_dataflow_set (&VTI (bb)->out);
+    }
+}
+
+/* Add variable VAR to the hash table of changed variables and
+   if it has no locations delete it from hash table HTAB.  */
+
+static void
+variable_was_changed (variable var, htab_t htab)
+{
+  hashval_t hash = VARIABLE_HASH_VAL (var->decl);
+
+  if (emit_notes)
+    {
+      variable *slot;
+
+      slot = (variable *) htab_find_slot_with_hash (changed_variables,
+						    var->decl, hash, INSERT);
+
+      if (htab && var->n_var_parts == 0)
+	{
+	  variable empty_var;
+	  void **old;
+
+	  empty_var = pool_alloc (var_pool);
+	  empty_var->decl = var->decl;
+	  empty_var->n_var_parts = 0;
+	  *slot = empty_var;
+
+	  old = htab_find_slot_with_hash (htab, var->decl, hash,
+					  NO_INSERT);
+	  if (old)
+	    htab_clear_slot (htab, old);
+	}
+      else
+	{
+	  *slot = var;
+	}
+    }
+  else
+    {
+#ifdef ENABLE_CHECKING
+      if (!htab)
+	abort ();
+#endif
+      if (var->n_var_parts == 0)
+	{
+	  void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
+						  NO_INSERT);
+	  if (slot)
+	    htab_clear_slot (htab, slot);
+	}
+    }
+}
+
+/* Set the location of frame_base_decl to LOC in dataflow set SET.  This
+   function expects that
+   frame_base_decl has already one location for offset 0 in the variable table.
+ */
+
+static void
+set_frame_base_location (dataflow_set *set, rtx loc)
+{
+  variable var;
+  
+  var = htab_find_with_hash (set->vars, frame_base_decl,
+			     VARIABLE_HASH_VAL (frame_base_decl));
+#ifdef ENABLE_CHECKING
+  if (!var)
+    abort ();
+  if (var->n_var_parts != 1)
+    abort ();
+  if (var->var_part[0].offset != 0)
+    abort ();
+  if (!var->var_part[0].loc_chain)
+    abort ();
+#endif
+
+  var->var_part[0].loc_chain->loc = loc;
+  variable_was_changed (var, set->vars);
+}
+
+/* Set the part of variable's location in the dataflow set SET.  The variable
+   part is specified by variable's declaration DECL and offset OFFSET and the
+   part's location by LOC.  */
+
+static void
+set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset)
+{
+  int pos, low, high;
+  location_chain node, prev, next;
+  variable var;
+  void **slot;
+  
+  slot = htab_find_slot_with_hash (set->vars, decl,
+				   VARIABLE_HASH_VAL (decl), INSERT);
+  if (!*slot)
+    {
+      /* Create new variable information.  */
+      var = pool_alloc (var_pool);
+      var->decl = decl;
+      var->n_var_parts = 1;
+      var->var_part[0].offset = offset;
+      var->var_part[0].loc_chain = NULL;
+      var->var_part[0].cur_loc = NULL;
+      *slot = var;
+      pos = 0;
+    }
+  else
+    {
+      var = (variable) *slot;
+
+      /* Find the location part.  */
+      low = 0;
+      high = var->n_var_parts;
+      while (low != high)
+	{
+	  pos = (low + high) / 2;
+	  if (var->var_part[pos].offset < offset)
+	    low = pos + 1;
+	  else
+	    high = pos;
+	}
+      pos = low;
+
+      if (pos == var->n_var_parts || var->var_part[pos].offset != offset)
+	{
+	  /* We have not find the location part, new one will be created.  */
+
+#ifdef ENABLE_CHECKING
+	  /* We track only variables whose size is <= MAX_VAR_PARTS bytes
+	     thus there are at most MAX_VAR_PARTS different offsets.  */
+	  if (var->n_var_parts >= MAX_VAR_PARTS)
+	    abort ();
+#endif
+
+	  /* We have to move the elements of array starting at index low to the
+	     next position.  */
+	  for (high = var->n_var_parts; high > low; high--)
+	    var->var_part[high] = var->var_part[high - 1];
+
+	  var->n_var_parts++;
+	  var->var_part[pos].offset = offset;
+	  var->var_part[pos].loc_chain = NULL;
+	  var->var_part[pos].cur_loc = NULL;
+	}
+    }
+
+  /* Delete the location from list.  */
+  prev = NULL;
+  for (node = var->var_part[pos].loc_chain; node; node = next)
+    {
+      next = node->next;
+      if ((GET_CODE (node->loc) == REG && GET_CODE (loc) == REG
+	   && REGNO (node->loc) == REGNO (loc))
+	  || rtx_equal_p (node->loc, loc))
+	{
+	  if (prev)
+	    prev->next = next;
+	  else
+	    var->var_part[pos].loc_chain = next;
+	  pool_free (loc_chain_pool, node);
+	  break;
+	}
+      else
+	prev = node;
+    }
+
+  /* Add the location to the beginning.  */
+  node = pool_alloc (loc_chain_pool);
+  node->loc = loc;
+  node->next = var->var_part[pos].loc_chain;
+  var->var_part[pos].loc_chain = node;
+
+  /* If no location was emitted do so.  */
+  if (var->var_part[pos].cur_loc == NULL)
+    {
+      var->var_part[pos].cur_loc = loc;
+      variable_was_changed (var, set->vars);
+    }
+}
+
+/* Delete the part of variable's location from dataflow set SET.  The variable
+   part is specified by variable's declaration DECL and offset OFFSET and the
+   part's location by LOC.  */
+
+static void
+delete_variable_part (dataflow_set *set, rtx loc, tree decl,
+		      HOST_WIDE_INT offset)
+{
+  int pos, low, high;
+  void **slot;
+    
+  slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
+				   NO_INSERT);
+  if (slot)
+    {
+      variable var = (variable) *slot;
+
+      /* Find the location part.  */
+      low = 0;
+      high = var->n_var_parts;
+      while (low != high)
+	{
+	  pos = (low + high) / 2;
+	  if (var->var_part[pos].offset < offset)
+	    low = pos + 1;
+	  else
+	    high = pos;
+	}
+      pos = low;
+
+      if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
+	{
+	  location_chain node, prev, next;
+	  bool changed;
+
+	  /* Delete the location part.  */
+	  prev = NULL;
+	  for (node = var->var_part[pos].loc_chain; node; node = next)
+	    {
+	      next = node->next;
+	      if ((GET_CODE (node->loc) == REG && GET_CODE (loc) == REG
+		   && REGNO (node->loc) == REGNO (loc))
+		  || rtx_equal_p (node->loc, loc))
+		{
+		  if (prev)
+		    prev->next = next;
+		  else
+		    var->var_part[pos].loc_chain = next;
+		  pool_free (loc_chain_pool, node);
+		  break;
+		}
+	      else
+		prev = node;
+	    }
+
+	  /* If we have deleted the location which was last emitted
+	     we have to emit new location so add the variable to set
+	     of changed variables.  */
+	  if (var->var_part[pos].cur_loc
+	      && ((GET_CODE (loc) == REG
+		   && GET_CODE (var->var_part[pos].cur_loc) == REG
+		   && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
+		  || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
+	    {
+	      changed = true;
+	      if (var->var_part[pos].loc_chain)
+		var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
+	    }
+	  else
+	    changed = false;
+
+	  if (var->var_part[pos].loc_chain == NULL)
+	    {
+	      var->n_var_parts--;
+	      while (pos < var->n_var_parts)
+		{
+		  var->var_part[pos] = var->var_part[pos + 1];
+		  pos++;
+		}
+	    }
+	  if (changed)
+	      variable_was_changed (var, set->vars);
+	}
+    }
+}
+
+/* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
+   additional parameters: WHERE specifies whether the note shall be emitted
+   before of after instruction INSN.  */
+
+static int
+emit_note_insn_var_location (void **varp, void *data)
+{
+  variable var = *(variable *) varp;
+  rtx insn = ((emit_note_data *)data)->insn;
+  enum emit_note_where where = ((emit_note_data *)data)->where;
+  rtx note;
+  int i;
+  bool complete;
+  HOST_WIDE_INT last_limit;
+  tree type_size_unit;
+
+#ifdef ENABLE_CHECKING
+  if (!var->decl)
+    abort ();
+#endif
+
+  complete = true;
+  last_limit = 0;
+  for (i = 0; i < var->n_var_parts; i++)
+    {
+      if (last_limit < var->var_part[i].offset)
+	{
+	  complete = false;
+	  break;
+	}
+      last_limit
+	= (var->var_part[i].offset
+	   + GET_MODE_SIZE (GET_MODE (var->var_part[i].loc_chain->loc)));
+    }
+  type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
+  if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
+    complete = false;
+
+  if (where == EMIT_NOTE_AFTER_INSN)
+    note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
+  else
+    note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
+
+  if (!complete)
+    {
+      NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
+						       NULL_RTX);
+    }
+  else if (var->n_var_parts == 1)
+    {
+      rtx expr_list
+	= gen_rtx_EXPR_LIST (VOIDmode,
+			     var->var_part[0].loc_chain->loc,
+			     GEN_INT (var->var_part[0].offset));
+
+      NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
+						       expr_list);
+    }
+  else if (var->n_var_parts)
+    {
+      rtx argp[MAX_VAR_PARTS];
+      rtx parallel;
+
+      for (i = 0; i < var->n_var_parts; i++)
+	argp[i] = gen_rtx_EXPR_LIST (VOIDmode, var->var_part[i].loc_chain->loc,
+				     GEN_INT (var->var_part[i].offset));
+      parallel = gen_rtx_PARALLEL (VOIDmode,
+				   gen_rtvec_v (var->n_var_parts, argp));
+      NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
+						       parallel);
+    }
+
+  htab_clear_slot (changed_variables, varp);
+
+  /* When there are no location parts the variable has been already
+     removed from hash table and a new empty variable was created.
+     Free the empty variable.  */
+  if (var->n_var_parts == 0)
+    {
+      pool_free (var_pool, var);
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
+   CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
+   shall be emitted before of after instruction INSN.  */
+
+static void
+emit_notes_for_changes (rtx insn, enum emit_note_where where)
+{
+  emit_note_data data;
+
+  data.insn = insn;
+  data.where = where;
+  htab_traverse (changed_variables, emit_note_insn_var_location, &data);
+}
+
+/* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
+   same variable in hash table DATA or is not there at all.  */
+
+static int
+emit_notes_for_differences_1 (void **slot, void *data)
+{
+  htab_t new_vars = (htab_t) data;
+  variable old_var, new_var;
+
+  old_var = *(variable *) slot;
+  new_var = (variable) htab_find_with_hash (new_vars, old_var->decl,
+					    VARIABLE_HASH_VAL (old_var->decl));
+
+  if (!new_var)
+    {
+      /* Variable has disappeared.  */
+      variable empty_var;
+
+      empty_var = pool_alloc (var_pool);
+      empty_var->decl = old_var->decl;
+      empty_var->n_var_parts = 0;
+      variable_was_changed (empty_var, NULL);
+    }
+  else if (variable_different_p (old_var, new_var))
+    {
+      variable_was_changed (new_var, NULL);
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
+   table DATA.  */
+
+static int
+emit_notes_for_differences_2 (void **slot, void *data)
+{
+  htab_t old_vars = (htab_t) data;
+  variable old_var, new_var;
+
+  new_var = *(variable *) slot;
+  old_var = (variable) htab_find_with_hash (old_vars, new_var->decl,
+					    VARIABLE_HASH_VAL (new_var->decl));
+  if (!old_var)
+    {
+      /* Variable has appeared.  */
+      variable_was_changed (new_var, NULL);
+    }
+
+  /* Continue traversing the hash table.  */
+  return 1;
+}
+
+/* Emit notes before INSN for differences between dataflow sets OLD_SET and
+   NEW_SET.  */
+
+static void
+emit_notes_for_differences (rtx insn, dataflow_set *old_set,
+			    dataflow_set *new_set)
+{
+  htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
+  htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
+  emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
+}
+
+/* Emit the notes for changes of location parts in the basic block BB.  */
+
+static void
+emit_notes_in_bb (basic_block bb)
+{
+  int i;
+  dataflow_set set;
+
+  dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
+  dataflow_set_copy (&set, &VTI (bb)->in);
+
+  for (i = 0; i < VTI (bb)->n_mos; i++)
+    {
+      rtx insn = VTI (bb)->mos[i].insn;
+
+      switch (VTI (bb)->mos[i].type)
+	{
+	  case MO_CALL:
+	    {
+	      int r;
+
+	      for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
+		if (TEST_HARD_REG_BIT (call_used_reg_set, r))
+		  {
+		    var_regno_delete (&set, r);
+		  }
+	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
+	    }
+	    break;
+
+	  case MO_USE:
+	  case MO_SET:
+	    {
+	      rtx loc = VTI (bb)->mos[i].u.loc;
+
+	      if (GET_CODE (loc) == REG)
+		var_reg_delete_and_set (&set, loc);
+	      else
+		var_mem_delete_and_set (&set, loc);
+
+	      if (VTI (bb)->mos[i].type == MO_USE)
+		emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
+	      else
+		emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
+	    }
+	    break;
+
+	  case MO_USE_NO_VAR:
+	  case MO_CLOBBER:
+	    {
+	      rtx loc = VTI (bb)->mos[i].u.loc;
+
+	      if (GET_CODE (loc) == REG)
+		var_reg_delete (&set, loc);
+	      else
+		var_mem_delete (&set, loc);
+
+	      if (VTI (bb)->mos[i].type == MO_USE_NO_VAR)
+		emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
+	      else
+		emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
+	    }
+	    break;
+
+	  case MO_ADJUST:
+	    {
+	      rtx base;
+
+	      set.stack_adjust += VTI (bb)->mos[i].u.adjust;
+	      base = gen_rtx_MEM (Pmode,
+				  gen_rtx_PLUS (Pmode, stack_pointer_rtx,
+						GEN_INT (set.stack_adjust)));
+	      set_frame_base_location (&set, base);
+	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
+	    }
+	    break;
+	}
+    }
+  dataflow_set_destroy (&set);
+}
+
+/* Emit notes for the whole function.  */
+
+static void
+vt_emit_notes (void)
+{
+  basic_block bb;
+  dataflow_set *last_out;
+  dataflow_set empty;
+
+#ifdef ENABLE_CHECKING
+  if (htab_elements (changed_variables))
+    abort ();
+#endif
+
+  /* Enable emitting notes by functions (mainly by set_variable_part and
+     delete_variable_part).  */
+  emit_notes = true;
+
+  dataflow_set_init (&empty, 7);
+  last_out = &empty;
+
+  FOR_EACH_BB (bb)
+    {
+      /* Emit the notes for changes of variable locations between two
+	 subsequent basic blocks.  */
+      emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
+
+      /* Emit the notes for the changes in the basic block itself.  */
+      emit_notes_in_bb (bb);
+
+      last_out = &VTI (bb)->out;
+    }
+  dataflow_set_destroy (&empty);
+  emit_notes = false;
+}
+
+/* If there is a declaration and offset associated with register/memory RTL
+   assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
+
+static bool
+vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
+{
+  if (GET_CODE (rtl) == REG)
+    {
+      if (REG_ATTRS (rtl))
+	{
+	  *declp = REG_EXPR (rtl);
+	  *offsetp = REG_OFFSET (rtl);
+	  return true;
+	}
+    }
+  else if (GET_CODE (rtl) == MEM)
+    {
+      if (MEM_ATTRS (rtl))
+	{
+	  *declp = MEM_EXPR (rtl);
+	  *offsetp = MEM_OFFSET (rtl) ? INTVAL (MEM_OFFSET (rtl)) : 0;
+	  return true;
+	}
+    }
+  return false;
+}
+
+/* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
+
+static void
+vt_add_function_parameters (void)
+{
+  tree parm;
+  HOST_WIDE_INT stack_adjust = 0;
+  
+  if (!frame_pointer_needed)
+    stack_adjust = prologue_stack_adjust ();
+
+  for (parm = DECL_ARGUMENTS (current_function_decl);
+       parm; parm = TREE_CHAIN (parm))
+    {
+      rtx decl_rtl = DECL_RTL_IF_SET (parm);
+      rtx incoming = DECL_INCOMING_RTL (parm);
+      tree decl;
+      HOST_WIDE_INT offset;
+      dataflow_set *in, *out;
+
+      if (TREE_CODE (parm) != PARM_DECL)
+	continue;
+
+      if (!DECL_NAME (parm))
+	continue;
+
+      if (!decl_rtl || !incoming)
+	continue;
+
+      if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
+	continue;
+
+      if (!vt_get_decl_and_offset (incoming, &decl, &offset))
+	if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
+	  continue;
+
+      if (!decl)
+	continue;
+
+      if (parm != decl)
+	abort ();
+
+      incoming = eliminate_regs (incoming, 0, NULL_RTX);
+      if (!frame_pointer_needed && GET_CODE (incoming) == MEM)
+	incoming = adjust_stack_reference (incoming, -stack_adjust);
+      in = &VTI (ENTRY_BLOCK_PTR)->in;
+      out = &VTI (ENTRY_BLOCK_PTR)->out;
+
+      if (GET_CODE (incoming) == REG)
+	{
+	  if (REGNO (incoming) >= FIRST_PSEUDO_REGISTER)
+	    abort ();
+	  attrs_list_insert (&in->regs[REGNO (incoming)],
+			     parm, offset, incoming);
+	  attrs_list_insert (&out->regs[REGNO (incoming)],
+			     parm, offset, incoming);
+	  set_variable_part (in, incoming, parm, offset);
+	  set_variable_part (out, incoming, parm, offset);
+	}
+      else if (GET_CODE (incoming) == MEM)
+	{
+	  set_variable_part (in, incoming, parm, offset);
+	  set_variable_part (out, incoming, parm, offset);
+	}
+    }
+}
+
+/* Allocate and initialize the data structures for variable tracking
+   and parse the RTL to get the micro operations.  */
+
+static void
+vt_initialize (void)
+{
+  basic_block bb;
+
+  alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
+
+  FOR_EACH_BB (bb)
+    {
+      rtx insn;
+      HOST_WIDE_INT pre, post;
+
+      /* Count the number of micro operations.  */
+      VTI (bb)->n_mos = 0;
+      for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
+	   insn = NEXT_INSN (insn))
+	{
+	  if (INSN_P (insn))
+	    {
+	      if (!frame_pointer_needed)
+		{
+		  insn_stack_adjust_offset_pre_post (insn, &pre, &post);
+		  if (pre)
+		    VTI (bb)->n_mos++;
+		  if (post)
+		    VTI (bb)->n_mos++;
+		}
+	      note_uses (&PATTERN (insn), count_uses_1, insn);
+	      note_stores (PATTERN (insn), count_stores, insn);
+	      if (GET_CODE (insn) == CALL_INSN)
+		VTI (bb)->n_mos++;
+	    }
+	}
+
+      /* Add the nicro-operations to the array.  */
+      VTI (bb)->mos = xmalloc (VTI (bb)->n_mos
+			       * sizeof (struct micro_operation_def));
+      VTI (bb)->n_mos = 0;
+      for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
+	   insn = NEXT_INSN (insn))
+	{
+	  if (INSN_P (insn))
+	    {
+	      int n1, n2;
+
+	      if (!frame_pointer_needed)
+		{
+		  insn_stack_adjust_offset_pre_post (insn, &pre, &post);
+		  if (pre)
+		    {
+		      micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+		      mo->type = MO_ADJUST;
+		      mo->u.adjust = pre;
+		      mo->insn = insn;
+		    }
+		}
+
+	      n1 = VTI (bb)->n_mos;
+	      note_uses (&PATTERN (insn), add_uses_1, insn);
+	      n2 = VTI (bb)->n_mos - 1;
+
+	      /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
+	      while (n1 < n2)
+		{
+		  while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
+		    n1++;
+		  while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
+		    n2--;
+		  if (n1 < n2)
+		    {
+		      micro_operation sw;
+
+		      sw = VTI (bb)->mos[n1];
+		      VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
+		      VTI (bb)->mos[n2] = sw;
+		    }
+		}
+
+	      if (GET_CODE (insn) == CALL_INSN)
+		{
+		  micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+		  mo->type = MO_CALL;
+		  mo->insn = insn;
+		}
+
+	      n1 = VTI (bb)->n_mos;
+	      note_stores (PATTERN (insn), add_stores, insn);
+	      n2 = VTI (bb)->n_mos - 1;
+
+	      /* Order the MO_SETs to be before MO_CLOBBERs.  */
+	      while (n1 < n2)
+		{
+		  while (n1 < n2 && VTI (bb)->mos[n1].type == MO_SET)
+		    n1++;
+		  while (n1 < n2 && VTI (bb)->mos[n2].type == MO_CLOBBER)
+		    n2--;
+		  if (n1 < n2)
+		    {
+		      micro_operation sw;
+
+		      sw = VTI (bb)->mos[n1];
+		      VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
+		      VTI (bb)->mos[n2] = sw;
+		    }
+		}
+
+	      if (!frame_pointer_needed && post)
+		{
+		  micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
+
+		  mo->type = MO_ADJUST;
+		  mo->u.adjust = post;
+		  mo->insn = insn;
+		}
+	    }
+	}
+    }
+
+  /* Init the IN and OUT sets.  */
+  FOR_ALL_BB (bb)
+    {
+      VTI (bb)->visited = false;
+      dataflow_set_init (&VTI (bb)->in, 7);
+      dataflow_set_init (&VTI (bb)->out, 7);
+    }
+
+  attrs_pool = create_alloc_pool ("attrs_def pool",
+				  sizeof (struct attrs_def), 1024);
+  var_pool = create_alloc_pool ("variable_def pool",
+				sizeof (struct variable_def), 64);
+  loc_chain_pool = create_alloc_pool ("location_chain_def pool",
+				      sizeof (struct location_chain_def),
+				      1024);
+  changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
+				   NULL);
+  vt_add_function_parameters ();
+
+  if (!frame_pointer_needed)
+    {
+      rtx base;
+
+      /* Create fake variable for tracking stack pointer changes.  */
+      frame_base_decl = make_node (VAR_DECL);
+      DECL_NAME (frame_base_decl) = get_identifier ("___frame_base_decl");
+      TREE_TYPE (frame_base_decl) = char_type_node;
+      DECL_ARTIFICIAL (frame_base_decl) = 1;
+
+      /* Set its initial "location".  */
+      base = gen_rtx_MEM (Pmode, stack_pointer_rtx);
+      set_variable_part (&VTI (ENTRY_BLOCK_PTR)->in, base, frame_base_decl, 0);
+      set_variable_part (&VTI (ENTRY_BLOCK_PTR)->out, base, frame_base_decl, 0);
+    }
+  else
+    {
+      frame_base_decl = NULL;
+    }
+}
+
+/* Free the data structures needed for variable tracking.  */
+
+static void
+vt_finalize (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB (bb)
+    {
+      free (VTI (bb)->mos);
+    }
+
+  FOR_ALL_BB (bb)
+    {
+      dataflow_set_destroy (&VTI (bb)->in);
+      dataflow_set_destroy (&VTI (bb)->out);
+    }
+  free_aux_for_blocks ();
+  free_alloc_pool (attrs_pool);
+  free_alloc_pool (var_pool);
+  free_alloc_pool (loc_chain_pool);
+  htab_delete (changed_variables);
+}
+
+/* The entry point to variable tracking pass.  */
+
+void
+variable_tracking_main (void)
+{
+  if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
+    return;
+
+  mark_dfs_back_edges ();
+  vt_initialize ();
+  if (!frame_pointer_needed)
+    {
+      if (!vt_stack_adjustments ())
+	{
+	  vt_finalize ();
+	  return;
+	}
+    }
+
+  vt_find_locations ();
+  vt_emit_notes ();
+
+  if (rtl_dump_file)
+    {
+      dump_dataflow_sets ();
+      dump_flow_info (rtl_dump_file);
+    }
+
+  vt_finalize ();
+}