OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [ddg.h] - Diff between revs 154 and 816

Go to most recent revision | Only display areas with differences | Details | Blame | View Log

Rev 154 Rev 816
/* DDG - Data Dependence Graph - interface.
/* DDG - Data Dependence Graph - interface.
   Copyright (C) 2004, 2007
   Copyright (C) 2004, 2007
   Free Software Foundation, Inc.
   Free Software Foundation, Inc.
   Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
   Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
 
 
This file is part of GCC.
This file is part of GCC.
 
 
GCC is free software; you can redistribute it and/or modify it under
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
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
Software Foundation; either version 3, or (at your option) any later
version.
version.
 
 
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.
for more details.
 
 
You should have received a copy of the GNU General Public License
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */
<http://www.gnu.org/licenses/>.  */
 
 
#ifndef GCC_DDG_H
#ifndef GCC_DDG_H
#define GCC_DDG_H
#define GCC_DDG_H
 
 
/* For sbitmap.  */
/* For sbitmap.  */
#include "sbitmap.h"
#include "sbitmap.h"
/* For basic_block.  */
/* For basic_block.  */
#include "basic-block.h"
#include "basic-block.h"
/* For struct df.  */
/* For struct df.  */
#include "df.h"
#include "df.h"
 
 
typedef struct ddg_node *ddg_node_ptr;
typedef struct ddg_node *ddg_node_ptr;
typedef struct ddg_edge *ddg_edge_ptr;
typedef struct ddg_edge *ddg_edge_ptr;
typedef struct ddg *ddg_ptr;
typedef struct ddg *ddg_ptr;
typedef struct ddg_scc *ddg_scc_ptr;
typedef struct ddg_scc *ddg_scc_ptr;
typedef struct ddg_all_sccs *ddg_all_sccs_ptr;
typedef struct ddg_all_sccs *ddg_all_sccs_ptr;
 
 
typedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type;
typedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type;
typedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP}
typedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP}
             dep_data_type;
             dep_data_type;
 
 
/* The following two macros enables direct access to the successors and
/* The following two macros enables direct access to the successors and
   predecessors bitmaps held in each ddg_node.  Do not make changes to
   predecessors bitmaps held in each ddg_node.  Do not make changes to
   these bitmaps, unless you want to change the DDG.  */
   these bitmaps, unless you want to change the DDG.  */
#define NODE_SUCCESSORS(x)  ((x)->successors)
#define NODE_SUCCESSORS(x)  ((x)->successors)
#define NODE_PREDECESSORS(x)  ((x)->predecessors)
#define NODE_PREDECESSORS(x)  ((x)->predecessors)
 
 
/* A structure that represents a node in the DDG.  */
/* A structure that represents a node in the DDG.  */
struct ddg_node
struct ddg_node
{
{
  /* Each node has a unique CUID index.  These indices increase monotonically
  /* Each node has a unique CUID index.  These indices increase monotonically
     (according to the order of the corresponding INSN in the BB), starting
     (according to the order of the corresponding INSN in the BB), starting
     from 0 with no gaps.  */
     from 0 with no gaps.  */
  int cuid;
  int cuid;
 
 
  /* The insn represented by the node.  */
  /* The insn represented by the node.  */
  rtx insn;
  rtx insn;
 
 
  /* A note preceding INSN (or INSN itself), such that all insns linked
  /* A note preceding INSN (or INSN itself), such that all insns linked
     from FIRST_NOTE until INSN (inclusive of both) are moved together
     from FIRST_NOTE until INSN (inclusive of both) are moved together
     when reordering the insns.  This takes care of notes that should
     when reordering the insns.  This takes care of notes that should
     continue to precede INSN.  */
     continue to precede INSN.  */
  rtx first_note;
  rtx first_note;
 
 
  /* Incoming and outgoing dependency edges.  */
  /* Incoming and outgoing dependency edges.  */
  ddg_edge_ptr in;
  ddg_edge_ptr in;
  ddg_edge_ptr out;
  ddg_edge_ptr out;
 
 
  /* Each bit corresponds to a ddg_node according to its cuid, and is
  /* Each bit corresponds to a ddg_node according to its cuid, and is
     set iff the node is a successor/predecessor of "this" node.  */
     set iff the node is a successor/predecessor of "this" node.  */
  sbitmap successors;
  sbitmap successors;
  sbitmap predecessors;
  sbitmap predecessors;
 
 
  /* For general use by algorithms manipulating the ddg.  */
  /* For general use by algorithms manipulating the ddg.  */
  union {
  union {
    int count;
    int count;
    void *info;
    void *info;
  } aux;
  } aux;
};
};
 
 
/* A structure that represents an edge in the DDG.  */
/* A structure that represents an edge in the DDG.  */
struct ddg_edge
struct ddg_edge
{
{
  /* The source and destination nodes of the dependency edge.  */
  /* The source and destination nodes of the dependency edge.  */
  ddg_node_ptr src;
  ddg_node_ptr src;
  ddg_node_ptr dest;
  ddg_node_ptr dest;
 
 
  /* TRUE, OUTPUT or ANTI dependency.  */
  /* TRUE, OUTPUT or ANTI dependency.  */
  dep_type type;
  dep_type type;
 
 
  /* REG or MEM dependency.  */
  /* REG or MEM dependency.  */
  dep_data_type data_type;
  dep_data_type data_type;
 
 
  /* Latency of the dependency.  */
  /* Latency of the dependency.  */
  int latency;
  int latency;
 
 
  /* The distance: number of loop iterations the dependency crosses.  */
  /* The distance: number of loop iterations the dependency crosses.  */
  int distance;
  int distance;
 
 
  /* The following two fields are used to form a linked list of the in/out
  /* The following two fields are used to form a linked list of the in/out
     going edges to/from each node.  */
     going edges to/from each node.  */
  ddg_edge_ptr next_in;
  ddg_edge_ptr next_in;
  ddg_edge_ptr next_out;
  ddg_edge_ptr next_out;
 
 
  /* For general use by algorithms manipulating the ddg.  */
  /* For general use by algorithms manipulating the ddg.  */
  union {
  union {
    int count;
    int count;
    void *info;
    void *info;
  } aux;
  } aux;
};
};
 
 
/* This structure holds the Data Dependence Graph for a basic block.  */
/* This structure holds the Data Dependence Graph for a basic block.  */
struct ddg
struct ddg
{
{
  /* The basic block for which this DDG is built.  */
  /* The basic block for which this DDG is built.  */
  basic_block bb;
  basic_block bb;
 
 
  /* Number of instructions in the basic block.  */
  /* Number of instructions in the basic block.  */
  int num_nodes;
  int num_nodes;
 
 
  /* Number of load/store instructions in the BB - statistics.  */
  /* Number of load/store instructions in the BB - statistics.  */
  int num_loads;
  int num_loads;
  int num_stores;
  int num_stores;
 
 
  /* This array holds the nodes in the graph; it is indexed by the node
  /* This array holds the nodes in the graph; it is indexed by the node
     cuid, which follows the order of the instructions in the BB.  */
     cuid, which follows the order of the instructions in the BB.  */
  ddg_node_ptr nodes;
  ddg_node_ptr nodes;
 
 
  /* The branch closing the loop.  */
  /* The branch closing the loop.  */
  ddg_node_ptr closing_branch;
  ddg_node_ptr closing_branch;
 
 
  /* Build dependence edges for closing_branch, when set.  In certain cases,
  /* Build dependence edges for closing_branch, when set.  In certain cases,
     the closing branch can be dealt with separately from the insns of the
     the closing branch can be dealt with separately from the insns of the
     loop, and then no such deps are needed.  */
     loop, and then no such deps are needed.  */
  int closing_branch_deps;
  int closing_branch_deps;
 
 
  /* Array and number of backarcs (edges with distance > 0) in the DDG.  */
  /* Array and number of backarcs (edges with distance > 0) in the DDG.  */
  ddg_edge_ptr *backarcs;
  ddg_edge_ptr *backarcs;
  int num_backarcs;
  int num_backarcs;
};
};
 
 


/* Holds information on an SCC (Strongly Connected Component) of the DDG.  */
/* Holds information on an SCC (Strongly Connected Component) of the DDG.  */
struct ddg_scc
struct ddg_scc
{
{
  /* A bitmap that represents the nodes of the DDG that are in the SCC.  */
  /* A bitmap that represents the nodes of the DDG that are in the SCC.  */
  sbitmap nodes;
  sbitmap nodes;
 
 
  /* Array and number of backarcs (edges with distance > 0) in the SCC.  */
  /* Array and number of backarcs (edges with distance > 0) in the SCC.  */
  ddg_edge_ptr *backarcs;
  ddg_edge_ptr *backarcs;
  int num_backarcs;
  int num_backarcs;
 
 
  /* The maximum of (total_latency/total_distance) over all cycles in SCC.  */
  /* The maximum of (total_latency/total_distance) over all cycles in SCC.  */
  int recurrence_length;
  int recurrence_length;
};
};
 
 
/* This structure holds the SCCs of the DDG.  */
/* This structure holds the SCCs of the DDG.  */
struct ddg_all_sccs
struct ddg_all_sccs
{
{
  /* Array that holds the SCCs in the DDG, and their number.  */
  /* Array that holds the SCCs in the DDG, and their number.  */
  ddg_scc_ptr *sccs;
  ddg_scc_ptr *sccs;
  int num_sccs;
  int num_sccs;
 
 
  ddg_ptr ddg;
  ddg_ptr ddg;
};
};
 
 


ddg_ptr create_ddg (basic_block, struct df *, int closing_branch_deps);
ddg_ptr create_ddg (basic_block, struct df *, int closing_branch_deps);
void free_ddg (ddg_ptr);
void free_ddg (ddg_ptr);
 
 
void print_ddg (FILE *, ddg_ptr);
void print_ddg (FILE *, ddg_ptr);
void vcg_print_ddg (FILE *, ddg_ptr);
void vcg_print_ddg (FILE *, ddg_ptr);
void print_ddg_edge (FILE *, ddg_edge_ptr);
void print_ddg_edge (FILE *, ddg_edge_ptr);
 
 
ddg_node_ptr get_node_of_insn (ddg_ptr, rtx);
ddg_node_ptr get_node_of_insn (ddg_ptr, rtx);
 
 
void find_successors (sbitmap result, ddg_ptr, sbitmap);
void find_successors (sbitmap result, ddg_ptr, sbitmap);
void find_predecessors (sbitmap result, ddg_ptr, sbitmap);
void find_predecessors (sbitmap result, ddg_ptr, sbitmap);
 
 
ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr);
ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr);
void free_ddg_all_sccs (ddg_all_sccs_ptr);
void free_ddg_all_sccs (ddg_all_sccs_ptr);
 
 
int find_nodes_on_paths (sbitmap result, ddg_ptr, sbitmap from, sbitmap to);
int find_nodes_on_paths (sbitmap result, ddg_ptr, sbitmap from, sbitmap to);
int longest_simple_path (ddg_ptr, int from, int to, sbitmap via);
int longest_simple_path (ddg_ptr, int from, int to, sbitmap via);
 
 
#endif /* GCC_DDG_H */
#endif /* GCC_DDG_H */
 
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.