Subversion Repositories scarts

/* Dataflow support routines.

   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005

   Free Software Foundation, Inc.

   Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz,

                                    mhayes@redhat.com)

This file is part of GCC.

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

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

Software Foundation; either version 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.

OVERVIEW:

This file provides some dataflow routines for computing reaching defs,

upward exposed uses, live variables, def-use chains, and use-def

chains.  The global dataflow is performed using simple iterative

methods with a worklist and could be sped up by ordering the blocks

with a depth first search order.

A `struct ref' data structure (ref) is allocated for every register

reference (def or use) and this records the insn and bb the ref is

found within.  The refs are linked together in chains of uses and defs

for each insn and for each register.  Each ref also has a chain field

that links all the use refs for a def or all the def refs for a use.

This is used to create use-def or def-use chains.

USAGE:

Here's an example of using the dataflow routines.

      struct df *df;

      df = df_init ();

      df_analyze (df, 0, DF_ALL);

      df_dump (df, DF_ALL, stderr);

      df_finish (df);

df_init simply creates a poor man's object (df) that needs to be

passed to all the dataflow routines.  df_finish destroys this

object and frees up any allocated memory.   DF_ALL says to analyze

everything.

df_analyze performs the following:

1. Records defs and uses by scanning the insns in each basic block

   or by scanning the insns queued by df_insn_modify.

2. Links defs and uses into insn-def and insn-use chains.

3. Links defs and uses into reg-def and reg-use chains.

4. Assigns LUIDs to each insn (for modified blocks).

5. Calculates local reaching definitions.

6. Calculates global reaching definitions.

7. Creates use-def chains.

8. Calculates local reaching uses (upwards exposed uses).

9. Calculates global reaching uses.

10. Creates def-use chains.

11. Calculates local live registers.

12. Calculates global live registers.

13. Calculates register lifetimes and determines local registers.

PHILOSOPHY:

Note that the dataflow information is not updated for every newly

deleted or created insn.  If the dataflow information requires

updating then all the changed, new, or deleted insns needs to be

marked with df_insn_modify (or df_insns_modify) either directly or

indirectly (say through calling df_insn_delete).  df_insn_modify

marks all the modified insns to get processed the next time df_analyze

 is called.

Beware that tinkering with insns may invalidate the dataflow information.

The philosophy behind these routines is that once the dataflow

information has been gathered, the user should store what they require

before they tinker with any insn.  Once a reg is replaced, for example,

then the reg-def/reg-use chains will point to the wrong place.  Once a

whole lot of changes have been made, df_analyze can be called again

to update the dataflow information.  Currently, this is not very smart

with regard to propagating changes to the dataflow so it should not

be called very often.

DATA STRUCTURES:

The basic object is a REF (reference) and this may either be a DEF

(definition) or a USE of a register.

These are linked into a variety of lists; namely reg-def, reg-use,

  insn-def, insn-use, def-use, and use-def lists.  For example,

the reg-def lists contain all the refs that define a given register

while the insn-use lists contain all the refs used by an insn.

Note that the reg-def and reg-use chains are generally short (except for

the hard registers) and thus it is much faster to search these chains

rather than searching the def or use bitmaps.

If the insns are in SSA form then the reg-def and use-def lists

should only contain the single defining ref.

TODO:

1) Incremental dataflow analysis.

Note that if a loop invariant insn is hoisted (or sunk), we do not

need to change the def-use or use-def chains.  All we have to do is to

change the bb field for all the associated defs and uses and to

renumber the LUIDs for the original and new basic blocks of the insn.

When shadowing loop mems we create new uses and defs for new pseudos

so we do not affect the existing dataflow information.

My current strategy is to queue up all modified, created, or deleted

insns so when df_analyze is called we can easily determine all the new

or deleted refs.  Currently the global dataflow information is

recomputed from scratch but this could be propagated more efficiently.

2) Reduced memory requirements.

We could operate a pool of ref structures.  When a ref is deleted it

gets returned to the pool (say by linking on to a chain of free refs).

This will require a pair of bitmaps for defs and uses so that we can

tell which ones have been changed.  Alternatively, we could

periodically squeeze the def and use tables and associated bitmaps and

renumber the def and use ids.

3) Ordering of reg-def and reg-use lists.

Should the first entry in the def list be the first def (within a BB)?

Similarly, should the first entry in the use list be the last use

(within a BB)?

4) Working with a sub-CFG.

Often the whole CFG does not need to be analyzed, for example,

when optimizing a loop, only certain registers are of interest.

Perhaps there should be a bitmap argument to df_analyze to specify

which registers should be analyzed?

NOTES:

Embedded addressing side-effects, such as POST_INC or PRE_INC, generate

both a use and a def.  These are both marked read/write to show that they

are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))

will generate a use of reg 42 followed by a def of reg 42 (both marked

read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))

generates a use of reg 41 then a def of reg 41 (both marked read/write),

even though reg 41 is decremented before it is used for the memory

address in this second example.

A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG

for which the number of word_mode units covered by the outer mode is

smaller than that covered by the inner mode, invokes a read-modify-write.

operation.  We generate both a use and a def and again mark them

read/write.

Paradoxical subreg writes don't leave a trace of the old content, so they

are write-only operations.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "tm_p.h"

#include "insn-config.h"

#include "recog.h"

#include "function.h"

#include "regs.h"

#include "alloc-pool.h"

#include "hard-reg-set.h"

#include "basic-block.h"

#include "sbitmap.h"

#include "bitmap.h"

#include "df.h"

#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE)    \

  do                                                    \

    {                                                   \

      unsigned int node_;                               \

      bitmap_iterator bi;                               \

      EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, bi) \

        {                                               \

          (BB) = BASIC_BLOCK (node_);                   \

          CODE;                                         \

        }                                               \

    }                                                   \

  while (0)

static alloc_pool df_ref_pool;

static alloc_pool df_link_pool;

static struct df *ddf;

static void df_reg_table_realloc (struct df *, int);

static void df_insn_table_realloc (struct df *, unsigned int);

static void df_bb_table_realloc (struct df *, unsigned int);

static void df_bitmaps_alloc (struct df *, bitmap, int);

static void df_bitmaps_free (struct df *, int);

static void df_free (struct df *);

static void df_alloc (struct df *, int);

static rtx df_reg_use_gen (unsigned int);

static inline struct df_link *df_link_create (struct ref *, struct df_link *);

static struct df_link *df_ref_unlink (struct df_link **, struct ref *);

static void df_def_unlink (struct df *, struct ref *);

static void df_use_unlink (struct df *, struct ref *);

static void df_insn_refs_unlink (struct df *, basic_block, rtx);

#if 0

static void df_bb_refs_unlink (struct df *, basic_block);

static void df_refs_unlink (struct df *, bitmap);

#endif

static struct ref *df_ref_create (struct df *, rtx, rtx *, rtx,

                                  enum df_ref_type, enum df_ref_flags);

static void df_ref_record_1 (struct df *, rtx, rtx *, rtx, enum df_ref_type,

                             enum df_ref_flags);

static void df_ref_record (struct df *, rtx, rtx *, rtx, enum df_ref_type,

                           enum df_ref_flags);

static void df_def_record_1 (struct df *, rtx, basic_block, rtx);

static void df_defs_record (struct df *, rtx, basic_block, rtx);

static void df_uses_record (struct df *, rtx *, enum df_ref_type,

                            basic_block, rtx, enum df_ref_flags);

static void df_insn_refs_record (struct df *, basic_block, rtx);

static void df_bb_refs_record (struct df *, basic_block);

static void df_refs_record (struct df *, bitmap);

static void df_bb_reg_def_chain_create (struct df *, basic_block);

static void df_reg_def_chain_create (struct df *, bitmap, bool);

static void df_bb_reg_use_chain_create (struct df *, basic_block);

static void df_reg_use_chain_create (struct df *, bitmap, bool);

static void df_bb_du_chain_create (struct df *, basic_block, bitmap);

static void df_du_chain_create (struct df *, bitmap);

static void df_bb_ud_chain_create (struct df *, basic_block);

static void df_ud_chain_create (struct df *, bitmap);

static void df_bb_rd_local_compute (struct df *, basic_block, bitmap);

static void df_rd_local_compute (struct df *, bitmap);

static void df_bb_ru_local_compute (struct df *, basic_block);

static void df_ru_local_compute (struct df *, bitmap);

static void df_bb_lr_local_compute (struct df *, basic_block);

static void df_lr_local_compute (struct df *, bitmap);

static void df_bb_reg_info_compute (struct df *, basic_block, bitmap);

static void df_reg_info_compute (struct df *, bitmap);

static int df_bb_luids_set (struct df *df, basic_block);

static int df_luids_set (struct df *df, bitmap);

static int df_modified_p (struct df *, bitmap);

static int df_refs_queue (struct df *);

static int df_refs_process (struct df *);

static int df_bb_refs_update (struct df *, basic_block);

static int df_refs_update (struct df *, bitmap);

static void df_analyze_1 (struct df *, bitmap, int, int);

static void df_insns_modify (struct df *, basic_block, rtx, rtx);

static int df_rtx_mem_replace (rtx *, void *);

static int df_rtx_reg_replace (rtx *, void *);

void df_refs_reg_replace (struct df *, bitmap, struct df_link *, rtx, rtx);

static int df_def_dominates_all_uses_p (struct df *, struct ref *def);

static int df_def_dominates_uses_p (struct df *, struct ref *def, bitmap);

static struct ref *df_bb_insn_regno_last_use_find (struct df *, basic_block,

                                                   rtx, unsigned int);

static struct ref *df_bb_insn_regno_first_def_find (struct df *, basic_block,

                                                    rtx, unsigned int);

static void df_chain_dump (struct df_link *, FILE *file);

static void df_chain_dump_regno (struct df_link *, FILE *file);

static void df_regno_debug (struct df *, unsigned int, FILE *);

static void df_ref_debug (struct df *, struct ref *, FILE *);

static void df_rd_transfer_function (int, int *, void *, void *, void *,

                                     void *, void *);

static void df_ru_transfer_function (int, int *, void *, void *, void *,

                                     void *, void *);

static void df_lr_transfer_function (int, int *, void *, void *, void *,

                                     void *, void *);

static void hybrid_search (basic_block, struct dataflow *,

                           sbitmap, sbitmap, sbitmap);

/* Local memory allocation/deallocation routines.  */

/* Increase the insn info table to have space for at least SIZE + 1

   elements.  */

static void

df_insn_table_realloc (struct df *df, unsigned int size)

{

  size++;

  if (size <= df->insn_size)

    return;

  /* Make the table a little larger than requested, so we do not need

     to enlarge it so often.  */

  size += df->insn_size / 4;

  df->insns = xrealloc (df->insns, size * sizeof (struct insn_info));

  memset (df->insns + df->insn_size, 0,

          (size - df->insn_size) * sizeof (struct insn_info));

  df->insn_size = size;

  if (! df->insns_modified)

    {

      df->insns_modified = BITMAP_ALLOC (NULL);

      bitmap_zero (df->insns_modified);

    }

}

/* Increase the bb info table to have space for at least SIZE + 1

   elements.  */

static void

df_bb_table_realloc (struct df *df, unsigned int size)

{

  size++;

  if (size <= df->n_bbs)

    return;

  /* Make the table a little larger than requested, so we do not need

     to enlarge it so often.  */

  size += df->n_bbs / 4;

  df->bbs = xrealloc (df->bbs, size * sizeof (struct bb_info));

  memset (df->bbs + df->n_bbs, 0, (size - df->n_bbs) * sizeof (struct bb_info));

  df->n_bbs = size;

}

/* Increase the reg info table by SIZE more elements.  */

static void

df_reg_table_realloc (struct df *df, int size)

{

  /* Make table 25 percent larger by default.  */

  if (! size)

    size = df->reg_size / 4;

  size += df->reg_size;

  if (size < max_reg_num ())

    size = max_reg_num ();

  df->regs = xrealloc (df->regs, size * sizeof (struct reg_info));

  df->reg_def_last = xrealloc (df->reg_def_last,

                               size * sizeof (struct ref *));

  /* Zero the new entries.  */

  memset (df->regs + df->reg_size, 0,

          (size - df->reg_size) * sizeof (struct reg_info));

  df->reg_size = size;

}

/* Allocate bitmaps for each basic block.  */

static void

df_bitmaps_alloc (struct df *df, bitmap blocks, int flags)

{

  basic_block bb;

  df->n_defs = df->def_id;

  df->n_uses = df->use_id;

  if (!blocks)

    blocks = df->all_blocks;

  FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,

    {

      struct bb_info *bb_info = DF_BB_INFO (df, bb);

      if (flags & DF_RD)

        {

          if (!bb_info->rd_in)

            {

              /* Allocate bitmaps for reaching definitions.  */

              bb_info->rd_kill = BITMAP_ALLOC (NULL);

              bb_info->rd_gen = BITMAP_ALLOC (NULL);

              bb_info->rd_in = BITMAP_ALLOC (NULL);

              bb_info->rd_out = BITMAP_ALLOC (NULL);

            }

          else

            {

              bitmap_clear (bb_info->rd_kill);

              bitmap_clear (bb_info->rd_gen);

              bitmap_clear (bb_info->rd_in);

              bitmap_clear (bb_info->rd_out);

            }

        }

      if (flags & DF_RU)

        {

          if (!bb_info->ru_in)

            {

              /* Allocate bitmaps for upward exposed uses.  */

              bb_info->ru_kill = BITMAP_ALLOC (NULL);

              bb_info->ru_gen = BITMAP_ALLOC (NULL);

              bb_info->ru_in = BITMAP_ALLOC (NULL);

              bb_info->ru_out = BITMAP_ALLOC (NULL);

            }

          else

            {

              bitmap_clear (bb_info->ru_kill);

              bitmap_clear (bb_info->ru_gen);

              bitmap_clear (bb_info->ru_in);

              bitmap_clear (bb_info->ru_out);

            }

        }

      if (flags & DF_LR)

        {

          if (!bb_info->lr_in)

            {

              /* Allocate bitmaps for live variables.  */

              bb_info->lr_def = BITMAP_ALLOC (NULL);

              bb_info->lr_use = BITMAP_ALLOC (NULL);

              bb_info->lr_in = BITMAP_ALLOC (NULL);

              bb_info->lr_out = BITMAP_ALLOC (NULL);

            }

          else

            {

              bitmap_clear (bb_info->lr_def);

              bitmap_clear (bb_info->lr_use);

              bitmap_clear (bb_info->lr_in);

              bitmap_clear (bb_info->lr_out);

            }

        }

    });

}

/* Free bitmaps for each basic block.  */

static void

df_bitmaps_free (struct df *df, int flags)

{

  basic_block bb;

  FOR_EACH_BB (bb)

    {

      struct bb_info *bb_info = DF_BB_INFO (df, bb);

      if (!bb_info)

        continue;

      if ((flags & DF_RD) && bb_info->rd_in)

        {

          /* Free bitmaps for reaching definitions.  */

          BITMAP_FREE (bb_info->rd_kill);

          bb_info->rd_kill = NULL;

          BITMAP_FREE (bb_info->rd_gen);

          bb_info->rd_gen = NULL;

          BITMAP_FREE (bb_info->rd_in);

          bb_info->rd_in = NULL;

          BITMAP_FREE (bb_info->rd_out);

          bb_info->rd_out = NULL;

        }

      if ((flags & DF_RU) && bb_info->ru_in)

        {

          /* Free bitmaps for upward exposed uses.  */

          BITMAP_FREE (bb_info->ru_kill);

          bb_info->ru_kill = NULL;

          BITMAP_FREE (bb_info->ru_gen);

          bb_info->ru_gen = NULL;

          BITMAP_FREE (bb_info->ru_in);

          bb_info->ru_in = NULL;

          BITMAP_FREE (bb_info->ru_out);

          bb_info->ru_out = NULL;

        }

      if ((flags & DF_LR) && bb_info->lr_in)

        {

          /* Free bitmaps for live variables.  */

          BITMAP_FREE (bb_info->lr_def);

          bb_info->lr_def = NULL;

          BITMAP_FREE (bb_info->lr_use);

          bb_info->lr_use = NULL;

          BITMAP_FREE (bb_info->lr_in);

          bb_info->lr_in = NULL;

          BITMAP_FREE (bb_info->lr_out);

          bb_info->lr_out = NULL;

        }

    }

  df->flags &= ~(flags & (DF_RD | DF_RU | DF_LR));

}

/* Allocate and initialize dataflow memory.  */

static void

df_alloc (struct df *df, int n_regs)

{

  int n_insns;

  basic_block bb;

  df_link_pool = create_alloc_pool ("df_link pool", sizeof (struct df_link),

                                    100);

  df_ref_pool  = create_alloc_pool ("df_ref pool", sizeof (struct ref), 100);

  /* Perhaps we should use LUIDs to save memory for the insn_refs

     table.  This is only a small saving; a few pointers.  */

  n_insns = get_max_uid () + 1;

  df->def_id = 0;

  df->n_defs = 0;

  /* Approximate number of defs by number of insns.  */

  df->def_size = n_insns;

  df->defs = xmalloc (df->def_size * sizeof (*df->defs));

  df->use_id = 0;

  df->n_uses = 0;

  /* Approximate number of uses by twice number of insns.  */

  df->use_size = n_insns * 2;

  df->uses = xmalloc (df->use_size * sizeof (*df->uses));

  df->n_regs = n_regs;

  df->n_bbs = last_basic_block;

  /* Allocate temporary working array used during local dataflow analysis.  */

  df_insn_table_realloc (df, n_insns);

  df_reg_table_realloc (df, df->n_regs);

  df->bbs_modified = BITMAP_ALLOC (NULL);

  bitmap_zero (df->bbs_modified);

  df->flags = 0;

  df->bbs = xcalloc (last_basic_block, sizeof (struct bb_info));

  df->all_blocks = BITMAP_ALLOC (NULL);

  FOR_EACH_BB (bb)

    bitmap_set_bit (df->all_blocks, bb->index);

}

/* Free all the dataflow info.  */

static void

df_free (struct df *df)

{

  df_bitmaps_free (df, DF_ALL);

  if (df->bbs)

    free (df->bbs);

  df->bbs = 0;

  if (df->insns)

    free (df->insns);

  df->insns = 0;

  df->insn_size = 0;

  if (df->defs)

    free (df->defs);

  df->defs = 0;

  df->def_size = 0;

  df->def_id = 0;

  if (df->uses)

    free (df->uses);

  df->uses = 0;

  df->use_size = 0;

  df->use_id = 0;

  if (df->regs)

    free (df->regs);

  df->regs = 0;

  df->reg_size = 0;

  BITMAP_FREE (df->bbs_modified);

  df->bbs_modified = 0;

  BITMAP_FREE (df->insns_modified);

  df->insns_modified = 0;

  BITMAP_FREE (df->all_blocks);

  df->all_blocks = 0;

  free_alloc_pool (df_ref_pool);

  free_alloc_pool (df_link_pool);

}

/* Local miscellaneous routines.  */

/* Return a USE for register REGNO.  */

static rtx df_reg_use_gen (unsigned int regno)

{

  rtx reg;

  rtx use;

  reg = regno_reg_rtx[regno];

  use = gen_rtx_USE (GET_MODE (reg), reg);

  return use;

}

/* Local chain manipulation routines.  */

/* Create a link in a def-use or use-def chain.  */

static inline struct df_link *

df_link_create (struct ref *ref, struct df_link *next)

{

  struct df_link *link;

  link = pool_alloc (df_link_pool);

  link->next = next;

  link->ref = ref;

  return link;

}

/* Releases members of the CHAIN.  */

static void

free_reg_ref_chain (struct df_link **chain)

{

  struct df_link *act, *next;

  for (act = *chain; act; act = next)

    {

      next = act->next;

      pool_free (df_link_pool, act);

    }

  *chain = NULL;

}

/* Add REF to chain head pointed to by PHEAD.  */

static struct df_link *

df_ref_unlink (struct df_link **phead, struct ref *ref)

{

  struct df_link *link = *phead;

  if (link)

    {

      if (! link->next)

        {

          /* Only a single ref.  It must be the one we want.

             If not, the def-use and use-def chains are likely to

             be inconsistent.  */

          gcc_assert (link->ref == ref);

          /* Now have an empty chain.  */

          *phead = NULL;

        }

      else

        {

          /* Multiple refs.  One of them must be us.  */

          if (link->ref == ref)

            *phead = link->next;

          else

            {

              /* Follow chain.  */

              for (; link->next; link = link->next)

                {

                  if (link->next->ref == ref)

                    {

                      /* Unlink from list.  */

                      link->next = link->next->next;

                      return link->next;

                    }

                }

            }

        }

    }

  return link;

}

/* Unlink REF from all def-use/use-def chains, etc.  */

int

df_ref_remove (struct df *df, struct ref *ref)

{

  if (DF_REF_REG_DEF_P (ref))

    {

      df_def_unlink (df, ref);

      df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].defs, ref);

    }

  else