Subversion Repositories scarts

/* Convert RTL to assembler code and output it, for GNU compiler.

   Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,

   1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005

   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, 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301, USA.  */

/* This is the final pass of the compiler.

   It looks at the rtl code for a function and outputs assembler code.

   Call `final_start_function' to output the assembler code for function entry,

   `final' to output assembler code for some RTL code,

   `final_end_function' to output assembler code for function exit.

   If a function is compiled in several pieces, each piece is

   output separately with `final'.

   Some optimizations are also done at this level.

   Move instructions that were made unnecessary by good register allocation

   are detected and omitted from the output.  (Though most of these

   are removed by the last jump pass.)

   Instructions to set the condition codes are omitted when it can be

   seen that the condition codes already had the desired values.

   In some cases it is sufficient if the inherited condition codes

   have related values, but this may require the following insn

   (the one that tests the condition codes) to be modified.

   The code for the function prologue and epilogue are generated

   directly in assembler by the target functions function_prologue and

   function_epilogue.  Those instructions never exist as rtl.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "rtl.h"

#include "tm_p.h"

#include "regs.h"

#include "insn-config.h"

#include "insn-attr.h"

#include "recog.h"

#include "conditions.h"

#include "flags.h"

#include "real.h"

#include "hard-reg-set.h"

#include "output.h"

#include "except.h"

#include "function.h"

#include "toplev.h"

#include "reload.h"

#include "intl.h"

#include "basic-block.h"

#include "target.h"

#include "debug.h"

#include "expr.h"

#include "cfglayout.h"

#include "tree-pass.h"

#include "timevar.h"

#include "cgraph.h"

#include "coverage.h"

#ifdef XCOFF_DEBUGGING_INFO

#include "xcoffout.h"           /* Needed for external data

                                   declarations for e.g. AIX 4.x.  */

#endif

#if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)

#include "dwarf2out.h"

#endif

#ifdef DBX_DEBUGGING_INFO

#include "dbxout.h"

#endif

#ifdef SDB_DEBUGGING_INFO

#include "sdbout.h"

#endif

/* If we aren't using cc0, CC_STATUS_INIT shouldn't exist.  So define a

   null default for it to save conditionalization later.  */

#ifndef CC_STATUS_INIT

#define CC_STATUS_INIT

#endif

/* How to start an assembler comment.  */

#ifndef ASM_COMMENT_START

#define ASM_COMMENT_START ";#"

#endif

/* Is the given character a logical line separator for the assembler?  */

#ifndef IS_ASM_LOGICAL_LINE_SEPARATOR

#define IS_ASM_LOGICAL_LINE_SEPARATOR(C) ((C) == ';')

#endif

#ifndef JUMP_TABLES_IN_TEXT_SECTION

#define JUMP_TABLES_IN_TEXT_SECTION 0

#endif

#if defined(READONLY_DATA_SECTION) || defined(READONLY_DATA_SECTION_ASM_OP)

#define HAVE_READONLY_DATA_SECTION 1

#else

#define HAVE_READONLY_DATA_SECTION 0

#endif

/* Bitflags used by final_scan_insn.  */

#define SEEN_BB         1

#define SEEN_NOTE       2

#define SEEN_EMITTED    4

/* Last insn processed by final_scan_insn.  */

static rtx debug_insn;

rtx current_output_insn;

/* Line number of last NOTE.  */

static int last_linenum;

/* Highest line number in current block.  */

static int high_block_linenum;

/* Likewise for function.  */

static int high_function_linenum;

/* Filename of last NOTE.  */

static const char *last_filename;

/* Whether to force emission of a line note before the next insn.  */

static bool force_source_line = false;

extern int length_unit_log; /* This is defined in insn-attrtab.c.  */

/* Nonzero while outputting an `asm' with operands.

   This means that inconsistencies are the user's fault, so don't die.

   The precise value is the insn being output, to pass to error_for_asm.  */

rtx this_is_asm_operands;

/* Number of operands of this insn, for an `asm' with operands.  */

static unsigned int insn_noperands;

/* Compare optimization flag.  */

static rtx last_ignored_compare = 0;

/* Assign a unique number to each insn that is output.

   This can be used to generate unique local labels.  */

static int insn_counter = 0;

#ifdef HAVE_cc0

/* This variable contains machine-dependent flags (defined in tm.h)

   set and examined by output routines

   that describe how to interpret the condition codes properly.  */

CC_STATUS cc_status;

/* During output of an insn, this contains a copy of cc_status

   from before the insn.  */

CC_STATUS cc_prev_status;

#endif

/* Indexed by hardware reg number, is 1 if that register is ever

   used in the current function.

   In life_analysis, or in stupid_life_analysis, this is set

   up to record the hard regs used explicitly.  Reload adds

   in the hard regs used for holding pseudo regs.  Final uses

   it to generate the code in the function prologue and epilogue

   to save and restore registers as needed.  */

char regs_ever_live[FIRST_PSEUDO_REGISTER];

/* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.

   Unlike regs_ever_live, elements of this array corresponding to

   eliminable regs like the frame pointer are set if an asm sets them.  */

char regs_asm_clobbered[FIRST_PSEUDO_REGISTER];

/* Nonzero means current function must be given a frame pointer.

   Initialized in function.c to 0.  Set only in reload1.c as per

   the needs of the function.  */

int frame_pointer_needed;

/* Number of unmatched NOTE_INSN_BLOCK_BEG notes we have seen.  */

static int block_depth;

/* Nonzero if have enabled APP processing of our assembler output.  */

static int app_on;

/* If we are outputting an insn sequence, this contains the sequence rtx.

   Zero otherwise.  */

rtx final_sequence;

#ifdef ASSEMBLER_DIALECT

/* Number of the assembler dialect to use, starting at 0.  */

static int dialect_number;

#endif

#ifdef HAVE_conditional_execution

/* Nonnull if the insn currently being emitted was a COND_EXEC pattern.  */

rtx current_insn_predicate;

#endif

#ifdef HAVE_ATTR_length

static int asm_insn_count (rtx);

#endif

static void profile_function (FILE *);

static void profile_after_prologue (FILE *);

static bool notice_source_line (rtx);

static rtx walk_alter_subreg (rtx *);

static void output_asm_name (void);

static void output_alternate_entry_point (FILE *, rtx);

static tree get_mem_expr_from_op (rtx, int *);

static void output_asm_operand_names (rtx *, int *, int);

static void output_operand (rtx, int);

#ifdef LEAF_REGISTERS

static void leaf_renumber_regs (rtx);

#endif

#ifdef HAVE_cc0

static int alter_cond (rtx);

#endif

#ifndef ADDR_VEC_ALIGN

static int final_addr_vec_align (rtx);

#endif

#ifdef HAVE_ATTR_length

static int align_fuzz (rtx, rtx, int, unsigned);

#endif

/* Initialize data in final at the beginning of a compilation.  */

void

init_final (const char *filename ATTRIBUTE_UNUSED)

{

  app_on = 0;

  final_sequence = 0;

#ifdef ASSEMBLER_DIALECT

  dialect_number = ASSEMBLER_DIALECT;

#endif

}

/* Default target function prologue and epilogue assembler output.

   If not overridden for epilogue code, then the function body itself

   contains return instructions wherever needed.  */

void

default_function_pro_epilogue (FILE *file ATTRIBUTE_UNUSED,

                               HOST_WIDE_INT size ATTRIBUTE_UNUSED)

{

}

/* Default target hook that outputs nothing to a stream.  */

void

no_asm_to_stream (FILE *file ATTRIBUTE_UNUSED)

{

}

/* Enable APP processing of subsequent output.

   Used before the output from an `asm' statement.  */

void

app_enable (void)

{

  if (! app_on)

    {

      fputs (ASM_APP_ON, asm_out_file);

      app_on = 1;

    }

}

/* Disable APP processing of subsequent output.

   Called from varasm.c before most kinds of output.  */

void

app_disable (void)

{

  if (app_on)

    {

      fputs (ASM_APP_OFF, asm_out_file);

      app_on = 0;

    }

}

/* Return the number of slots filled in the current

   delayed branch sequence (we don't count the insn needing the

   delay slot).   Zero if not in a delayed branch sequence.  */

#ifdef DELAY_SLOTS

int

dbr_sequence_length (void)

{

  if (final_sequence != 0)

    return XVECLEN (final_sequence, 0) - 1;

  else

    return 0;

}

#endif

/* The next two pages contain routines used to compute the length of an insn

   and to shorten branches.  */

/* Arrays for insn lengths, and addresses.  The latter is referenced by

   `insn_current_length'.  */

static int *insn_lengths;

varray_type insn_addresses_;

/* Max uid for which the above arrays are valid.  */

static int insn_lengths_max_uid;

/* Address of insn being processed.  Used by `insn_current_length'.  */

int insn_current_address;

/* Address of insn being processed in previous iteration.  */

int insn_last_address;

/* known invariant alignment of insn being processed.  */

int insn_current_align;

/* After shorten_branches, for any insn, uid_align[INSN_UID (insn)]

   gives the next following alignment insn that increases the known

   alignment, or NULL_RTX if there is no such insn.

   For any alignment obtained this way, we can again index uid_align with

   its uid to obtain the next following align that in turn increases the

   alignment, till we reach NULL_RTX; the sequence obtained this way

   for each insn we'll call the alignment chain of this insn in the following

   comments.  */

struct label_alignment

{

  short alignment;

  short max_skip;

};

static rtx *uid_align;

static int *uid_shuid;

static struct label_alignment *label_align;

/* Indicate that branch shortening hasn't yet been done.  */

void

init_insn_lengths (void)

{

  if (uid_shuid)

    {

      free (uid_shuid);

      uid_shuid = 0;

    }

  if (insn_lengths)

    {

      free (insn_lengths);

      insn_lengths = 0;

      insn_lengths_max_uid = 0;

    }

#ifdef HAVE_ATTR_length

  INSN_ADDRESSES_FREE ();

#endif

  if (uid_align)

    {

      free (uid_align);

      uid_align = 0;

    }

}

/* Obtain the current length of an insn.  If branch shortening has been done,

   get its actual length.  Otherwise, use FALLBACK_FN to calcualte the

   length.  */

static inline int

get_attr_length_1 (rtx insn ATTRIBUTE_UNUSED,

                   int (*fallback_fn) (rtx) ATTRIBUTE_UNUSED)

{

#ifdef HAVE_ATTR_length

  rtx body;

  int i;

  int length = 0;

  if (insn_lengths_max_uid > INSN_UID (insn))

    return insn_lengths[INSN_UID (insn)];

  else

    switch (GET_CODE (insn))

      {

      case NOTE:

      case BARRIER:

      case CODE_LABEL:

        return 0;

      case CALL_INSN:

        length = fallback_fn (insn);

        break;

      case JUMP_INSN:

        body = PATTERN (insn);

        if (GET_CODE (body) == ADDR_VEC || GET_CODE (body) == ADDR_DIFF_VEC)

          {

            /* Alignment is machine-dependent and should be handled by

               ADDR_VEC_ALIGN.  */

          }

        else

          length = fallback_fn (insn);

        break;

      case INSN:

        body = PATTERN (insn);

        if (GET_CODE (body) == USE || GET_CODE (body) == CLOBBER)

          return 0;

        else if (GET_CODE (body) == ASM_INPUT || asm_noperands (body) >= 0)

          length = asm_insn_count (body) * fallback_fn (insn);

        else if (GET_CODE (body) == SEQUENCE)

          for (i = 0; i < XVECLEN (body, 0); i++)

            length += get_attr_length (XVECEXP (body, 0, i));

        else

          length = fallback_fn (insn);

        break;

      default:

        break;

      }

#ifdef ADJUST_INSN_LENGTH

  ADJUST_INSN_LENGTH (insn, length);

#endif

  return length;

#else /* not HAVE_ATTR_length */

  return 0;

#define insn_default_length 0

#define insn_min_length 0

#endif /* not HAVE_ATTR_length */

}

/* Obtain the current length of an insn.  If branch shortening has been done,

   get its actual length.  Otherwise, get its maximum length.  */

int

get_attr_length (rtx insn)

{

  return get_attr_length_1 (insn, insn_default_length);

}

/* Obtain the current length of an insn.  If branch shortening has been done,

   get its actual length.  Otherwise, get its minimum length.  */

int

get_attr_min_length (rtx insn)

{

  return get_attr_length_1 (insn, insn_min_length);

}

/* Code to handle alignment inside shorten_branches.  */

/* Here is an explanation how the algorithm in align_fuzz can give

   proper results:

   Call a sequence of instructions beginning with alignment point X

   and continuing until the next alignment point `block X'.  When `X'

   is used in an expression, it means the alignment value of the

   alignment point.

   Call the distance between the start of the first insn of block X, and

   the end of the last insn of block X `IX', for the `inner size of X'.

   This is clearly the sum of the instruction lengths.

   Likewise with the next alignment-delimited block following X, which we

   shall call block Y.

   Call the distance between the start of the first insn of block X, and

   the start of the first insn of block Y `OX', for the `outer size of X'.

   The estimated padding is then OX - IX.

   OX can be safely estimated as

           if (X >= Y)

                   OX = round_up(IX, Y)

           else

                   OX = round_up(IX, X) + Y - X

   Clearly est(IX) >= real(IX), because that only depends on the

   instruction lengths, and those being overestimated is a given.

   Clearly round_up(foo, Z) >= round_up(bar, Z) if foo >= bar, so

   we needn't worry about that when thinking about OX.

   When X >= Y, the alignment provided by Y adds no uncertainty factor

   for branch ranges starting before X, so we can just round what we have.

   But when X < Y, we don't know anything about the, so to speak,

   `middle bits', so we have to assume the worst when aligning up from an

   address mod X to one mod Y, which is Y - X.  */

#ifndef LABEL_ALIGN

#define LABEL_ALIGN(LABEL) align_labels_log

#endif

#ifndef LABEL_ALIGN_MAX_SKIP

#define LABEL_ALIGN_MAX_SKIP align_labels_max_skip

#endif

#ifndef LOOP_ALIGN

#define LOOP_ALIGN(LABEL) align_loops_log

#endif

#ifndef LOOP_ALIGN_MAX_SKIP

#define LOOP_ALIGN_MAX_SKIP align_loops_max_skip

#endif

#ifndef LABEL_ALIGN_AFTER_BARRIER

#define LABEL_ALIGN_AFTER_BARRIER(LABEL) 0

#endif

#ifndef LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP

#define LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP 0

#endif

#ifndef JUMP_ALIGN

#define JUMP_ALIGN(LABEL) align_jumps_log

#endif

#ifndef JUMP_ALIGN_MAX_SKIP

#define JUMP_ALIGN_MAX_SKIP align_jumps_max_skip

#endif

#ifndef ADDR_VEC_ALIGN

static int

final_addr_vec_align (rtx addr_vec)

{

  int align = GET_MODE_SIZE (GET_MODE (PATTERN (addr_vec)));

  if (align > BIGGEST_ALIGNMENT / BITS_PER_UNIT)

    align = BIGGEST_ALIGNMENT / BITS_PER_UNIT;

  return exact_log2 (align);

}

#define ADDR_VEC_ALIGN(ADDR_VEC) final_addr_vec_align (ADDR_VEC)

#endif

#ifndef INSN_LENGTH_ALIGNMENT

#define INSN_LENGTH_ALIGNMENT(INSN) length_unit_log

#endif

#define INSN_SHUID(INSN) (uid_shuid[INSN_UID (INSN)])

static int min_labelno, max_labelno;

#define LABEL_TO_ALIGNMENT(LABEL) \

  (label_align[CODE_LABEL_NUMBER (LABEL) - min_labelno].alignment)

#define LABEL_TO_MAX_SKIP(LABEL) \

  (label_align[CODE_LABEL_NUMBER (LABEL) - min_labelno].max_skip)

/* For the benefit of port specific code do this also as a function.  */

int

label_to_alignment (rtx label)

{

  return LABEL_TO_ALIGNMENT (label);

}

#ifdef HAVE_ATTR_length

/* The differences in addresses

   between a branch and its target might grow or shrink depending on

   the alignment the start insn of the range (the branch for a forward

   branch or the label for a backward branch) starts out on; if these

   differences are used naively, they can even oscillate infinitely.

   We therefore want to compute a 'worst case' address difference that

   is independent of the alignment the start insn of the range end

   up on, and that is at least as large as the actual difference.

   The function align_fuzz calculates the amount we have to add to the

   naively computed difference, by traversing the part of the alignment

   chain of the start insn of the range that is in front of the end insn

   of the range, and considering for each alignment the maximum amount

   that it might contribute to a size increase.

   For casesi tables, we also want to know worst case minimum amounts of

   address difference, in case a machine description wants to introduce

   some common offset that is added to all offsets in a table.

   For this purpose, align_fuzz with a growth argument of 0 computes the

   appropriate adjustment.  */

/* Compute the maximum delta by which the difference of the addresses of

   START and END might grow / shrink due to a different address for start

   which changes the size of alignment insns between START and END.

   KNOWN_ALIGN_LOG is the alignment known for START.

   GROWTH should be ~0 if the objective is to compute potential code size

   increase, and 0 if the objective is to compute potential shrink.

   The return value is undefined for any other value of GROWTH.  */

static int

align_fuzz (rtx start, rtx end, int known_align_log, unsigned int growth)

{

  int uid = INSN_UID (start);

  rtx align_label;

  int known_align = 1 << known_align_log;

  int end_shuid = INSN_SHUID (end);

  int fuzz = 0;

  for (align_label = uid_align[uid]; align_label; align_label = uid_align[uid])

    {

      int align_addr, new_align;

      uid = INSN_UID (align_label);

      align_addr = INSN_ADDRESSES (uid) - insn_lengths[uid];

      if (uid_shuid[uid] > end_shuid)

        break;

      known_align_log = LABEL_TO_ALIGNMENT (align_label);

      new_align = 1 << known_align_log;

      if (new_align < known_align)

        continue;

      fuzz += (-align_addr ^ growth) & (new_align - known_align);

      known_align = new_align;

    }

  return fuzz;

}

/* Compute a worst-case reference address of a branch so that it

   can be safely used in the presence of aligned labels.  Since the

   size of the branch itself is unknown, the size of the branch is

   not included in the range.  I.e. for a forward branch, the reference

   address is the end address of the branch as known from the previous

   branch shortening pass, minus a value to account for possible size

   increase due to alignment.  For a backward branch, it is the start

   address of the branch as known from the current pass, plus a value

   to account for possible size increase due to alignment.

   NB.: Therefore, the maximum offset allowed for backward branches needs

   to exclude the branch size.  */

int

insn_current_reference_address (rtx branch)

{

  rtx dest, seq;

  int seq_uid;

  if (! INSN_ADDRESSES_SET_P ())

    return 0;

  seq = NEXT_INSN (PREV_INSN (branch));

  seq_uid = INSN_UID (seq);

  if (!JUMP_P (branch))

    /* This can happen for example on the PA; the objective is to know the

       offset to address something in front of the start of the function.

       Thus, we can treat it like a backward branch.

       We assume here that FUNCTION_BOUNDARY / BITS_PER_UNIT is larger than

       any alignment we'd encounter, so we skip the call to align_fuzz.  */

    return insn_current_address;

  dest = JUMP_LABEL (branch);

  /* BRANCH has no proper alignment chain set, so use SEQ.

     BRANCH also has no INSN_SHUID.  */

  if (INSN_SHUID (seq) < INSN_SHUID (dest))

    {

      /* Forward branch.  */

      return (insn_last_address + insn_lengths[seq_uid]

              - align_fuzz (seq, dest, length_unit_log, ~0));

    }

  else

    {

      /* Backward branch.  */

      return (insn_current_address

              + align_fuzz (dest, seq, length_unit_log, ~0));

    }

}

#endif /* HAVE_ATTR_length */

void

compute_alignments (void)

{

  int log, max_skip, max_log;

  basic_block bb;

  if (label_align)

    {

      free (label_align);

      label_align = 0;

    }

  max_labelno = max_label_num ();

  min_labelno = get_first_label_num ();

  label_align = xcalloc (max_labelno - min_labelno + 1,

                         sizeof (struct label_alignment));

  /* If not optimizing or optimizing for size, don't assign any alignments.  */

  if (! optimize || optimize_size)

    return;

  FOR_EACH_BB (bb)

    {

      rtx label = BB_HEAD (bb);

      int fallthru_frequency = 0, branch_frequency = 0, has_fallthru = 0;

      edge e;

      edge_iterator ei;

      if (!LABEL_P (label)

          || probably_never_executed_bb_p (bb))

        continue;

      max_log = LABEL_ALIGN (label);

      max_skip = LABEL_ALIGN_MAX_SKIP;

      FOR_EACH_EDGE (e, ei, bb->preds)

        {

          if (e->flags & EDGE_FALLTHRU)

            has_fallthru = 1, fallthru_frequency += EDGE_FREQUENCY (e);

          else

            branch_frequency += EDGE_FREQUENCY (e);

        }

      /* There are two purposes to align block with no fallthru incoming edge:

         1) to avoid fetch stalls when branch destination is near cache boundary

         2) to improve cache efficiency in case the previous block is not executed

            (so it does not need to be in the cache).

         We to catch first case, we align frequently executed blocks.

         To catch the second, we align blocks that are executed more frequently

         than the predecessor and the predecessor is likely to not be executed

         when function is called.  */

      if (!has_fallthru

          && (branch_frequency > BB_FREQ_MAX / 10

              || (bb->frequency > bb->prev_bb->frequency * 10

                  && (bb->prev_bb->frequency

                      <= ENTRY_BLOCK_PTR->frequency / 2))))

        {

          log = JUMP_ALIGN (label);

          if (max_log < log)

            {

              max_log = log;

              max_skip = JUMP_ALIGN_MAX_SKIP;

            }

        }

      /* In case block is frequent and reached mostly by non-fallthru edge,

         align it.  It is most likely a first block of loop.  */

      if (has_fallthru

          && maybe_hot_bb_p (bb)

          && branch_frequency + fallthru_frequency > BB_FREQ_MAX / 10

          && branch_frequency > fallthru_frequency * 2)

        {

          log = LOOP_ALIGN (label);

          if (max_log < log)

            {

              max_log = log;

              max_skip = LOOP_ALIGN_MAX_SKIP;

            }

        }

      LABEL_TO_ALIGNMENT (label) = max_log;

      LABEL_TO_MAX_SKIP (label) = max_skip;

    }

}

struct tree_opt_pass pass_compute_alignments =

{

  NULL,                                 /* name */

  NULL,                                 /* gate */

  compute_alignments,                   /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                    /* static_pass_number */

  0,                                    /* tv_id */