This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Memory usage in compute_immediate_uses
On Tue, 2003-09-16 at 19:14, Daniel Jacobowitz wrote:
> On Tue, Sep 16, 2003 at 03:38:57PM -0400, Diego Novillo wrote:
> > On Tue, 2003-09-16 at 14:33, Daniel Jacobowitz wrote:
> >
> As for size: this isn't the ideal quantity to measure, but it was the
> quickest hack. The distribution of
> max (number of uses attached to any one statement in a function)
> with one sample per function:
> 3223 had no statements with uses at all.
> 27557 had a max of 1-4.
> 14334 had a max of 5-10.
> 7421 had a max of 11-100.
> 236 were between 101-678.
> 2 had 1274 (probably the same file in two stages).
> One greater than 2K: 4230, in interpret.cc.
>
> This suggests that a varray of size ten is not a good choice, but that
> a varray of another size would not be a much better choice.
Here's a minor reimplementation of the immediate_uses data structure.
Since the vast majority of gimple things have only one or two uses, I
tried to optimize more for those cases and not do a ggc_alloc().
in the data_flow_d structure, we were already burning 2 words for
reaching definition information which was never being used. So I deleted
to the 2 defs and added a 2 element vector for immediate_uses. This
leaves the structure footprint unchanged. I left all the comments there
for reaching defs in case we ever decide we want to implement them.
So, the first 2 uses added go straight into the dataflow structure now.
If more than 2 are needed, then we allocate the varray and use it for
the remaining uses. I also start it at 4 elements (which covers us up
to 6 uses) since I suspect that covers the vast majority of the
remaining stmts. Anything beyond that, well, we might end up with an
additional allocation.
The interface has been changed. Now there are 3 routines, and they are
used thusly:
dataflow_t df;
df = get_immediate_uses (stmt);
num = num_immediate_uses (df);
for (x = 0; x < num; x++)
tree stmt = immediate_use (df, x);
Its not a big difference, but it does appear to shave about a second off
the total compile time of libjava/interpret.cc on my machine. Hard to
say exactly where it comes from tho, it appears to be more of a
secondary effect than a direct effect. It should be a bit nice to the
garbage collector.
And since the interface is now abstracted away from the implementation,
its simple enough to fool around with the underlying implementation to
improve it in whatever way someone sees fit.
Bootstrapping and verifying now. I'll check it in when thats all done
(later this afternoon?) assuming no one has any issues.
Andrew
* tree-flow.h (struct dataflow_d): Remove reaching fields, add 2 element
vector of trees.
* tree-flow-inline.h (immediate_uses): Rename to get_immediate_uses,
return a dataflow object.
(reaching_defs): Remove until needed.
(num_immediate_uses): New. Return number of immediate uses.
(immediate_use): New. Return a specified immediate use.
* tree-dfa.c (add_immediate_use): Use new fields.
(dump_immediate_uses_for): Use new interface.
* tree-ssa-ccp.c (add_var_to_ssa_edges_worklist): Use new interface.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.160
diff -c -p -r1.1.4.160 tree-dfa.c
*** tree-dfa.c 17 Sep 2003 17:06:34 -0000 1.1.4.160
--- tree-dfa.c 19 Sep 2003 16:56:37 -0000
*************** static void
*** 1221,1235 ****
add_immediate_use (tree stmt, tree use_stmt)
{
stmt_ann_t ann = get_stmt_ann (stmt);
! if (ann->df == NULL)
{
! ann->df = ggc_alloc (sizeof (struct dataflow_d));
! memset ((void *) ann->df, 0, sizeof (*(ann->df)));
}
if (ann->df->immediate_uses == NULL)
! VARRAY_TREE_INIT (ann->df->immediate_uses, 10, "immediate_uses");
VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
}
--- 1221,1245 ----
add_immediate_use (tree stmt, tree use_stmt)
{
stmt_ann_t ann = get_stmt_ann (stmt);
+ struct dataflow_d *df;
! df = ann->df;
! if (df == NULL)
{
! df = ann->df = ggc_alloc (sizeof (struct dataflow_d));
! memset ((void *) df, 0, sizeof (struct dataflow_d));
! df->uses[0] = use_stmt;
! return;
! }
!
! if (!df->uses[1])
! {
! df->uses[1] = use_stmt;
! return;
}
if (ann->df->immediate_uses == NULL)
! VARRAY_TREE_INIT (ann->df->immediate_uses, 4, "immediate_uses");
VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
}
*************** debug_immediate_uses (void)
*** 1557,1576 ****
void
dump_immediate_uses_for (FILE *file, tree stmt)
{
! varray_type imm_uses = immediate_uses (stmt);
! if (imm_uses)
{
! size_t i;
fprintf (file, "-> ");
print_generic_stmt (file, stmt, TDF_SLIM);
fprintf (file, "\n");
! for (i = 0; i < VARRAY_ACTIVE_SIZE (imm_uses); i++)
{
fprintf (file, "\t");
! print_generic_stmt (file, VARRAY_TREE (imm_uses, i), TDF_SLIM);
fprintf (file, "\n");
}
--- 1567,1587 ----
void
dump_immediate_uses_for (FILE *file, tree stmt)
{
! dataflow_t df = get_immediate_uses (stmt);
! int num_imm_uses = num_immediate_uses (df);
! if (num_imm_uses > 0)
{
! int i;
fprintf (file, "-> ");
print_generic_stmt (file, stmt, TDF_SLIM);
fprintf (file, "\n");
! for (i = 0; i < num_imm_uses; i++)
{
fprintf (file, "\t");
! print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
fprintf (file, "\n");
}
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.50
diff -c -p -r1.1.2.50 tree-flow-inline.h
*** tree-flow-inline.h 17 Sep 2003 17:06:34 -0000 1.1.2.50
--- tree-flow-inline.h 19 Sep 2003 16:56:38 -0000
*************** addresses_taken (tree stmt)
*** 234,251 ****
return ann ? ann->addresses_taken : NULL;
}
! static inline varray_type
! immediate_uses (tree stmt)
{
stmt_ann_t ann = stmt_ann (stmt);
! return ann ? (ann->df ? ann->df->immediate_uses : NULL) : NULL;
}
! static inline varray_type
! reaching_defs (tree stmt)
{
! stmt_ann_t ann = stmt_ann (stmt);
! return ann ? (ann->df ? ann->df->reaching_defs : NULL) : NULL;
}
static inline bb_ann_t
--- 234,271 ----
return ann ? ann->addresses_taken : NULL;
}
! static dataflow_t
! get_immediate_uses (tree stmt)
{
stmt_ann_t ann = stmt_ann (stmt);
! return ann ? ann->df : NULL;
}
! static inline int
! num_immediate_uses (dataflow_t df)
{
! varray_type imm;
!
! if (!df)
! return 0;
!
! imm = df->immediate_uses;
! if (!imm)
! return df->uses[1] ? 2 : 1;
!
! return VARRAY_ACTIVE_SIZE (imm) + 2;
! }
!
! static inline tree
! immediate_use (dataflow_t df, int num)
! {
! #ifdef ENABLE_CHECKING
! if (num >= num_immediate_uses (df))
! abort ();
! #endif
! if (num < 2)
! return df->uses[num];
! return VARRAY_TREE (df->immediate_uses, num - 2);
}
static inline bb_ann_t
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.115
diff -c -p -r1.1.4.115 tree-flow.h
*** tree-flow.h 16 Sep 2003 03:08:08 -0000 1.1.4.115
--- tree-flow.h 19 Sep 2003 16:56:38 -0000
*************** struct dataflow_d GTY(())
*** 163,168 ****
--- 163,171 ----
statement. */
varray_type immediate_uses;
+ /* Use this array for very small numbers of uses instead of the varray. */
+ tree uses[2];
+
/* Reached uses. This is a list of all the possible program statements
that may be reached directly or indirectly by definitions made in this
statement. Notice that this is a superset of IMMEDIATE_USES.
*************** struct dataflow_d GTY(())
*** 179,185 ****
includes statement #5 because 'a1' could reach 'a3' via the PHI node
at statement #4. The set of REACHED_USES is then the transitive
closure over all the PHI nodes in the IMMEDIATE_USES set. */
- varray_type reached_uses;
/* Reaching definitions. Similarly to REACHED_USES, the set
REACHING_DEFS is the set of all the statements that make definitions
--- 182,187 ----
*************** struct dataflow_d GTY(())
*** 187,193 ****
similar entry for immediate definitions, as these are represented by
the SSA_NAME nodes themselves (each SSA_NAME node contains a pointer
to the statement that makes that definition). */
- varray_type reaching_defs;
};
typedef struct dataflow_d *dataflow_t;
--- 189,194 ----
*************** static inline varray_type vuse_ops (tree
*** 285,292 ****
static inline varray_type use_ops (tree);
static inline varray_type def_ops (tree);
static inline varray_type addresses_taken (tree);
! static inline varray_type immediate_uses (tree);
! static inline varray_type reaching_defs (tree);
static inline bool has_hidden_use (tree);
static inline void set_has_hidden_use (tree);
static inline tree parent_stmt (tree);
--- 286,294 ----
static inline varray_type use_ops (tree);
static inline varray_type def_ops (tree);
static inline varray_type addresses_taken (tree);
! static inline int num_immediate_uses (dataflow_t);
! static inline tree immediate_use (dataflow_t, int);
! static inline dataflow_t get_immediate_uses (tree);
static inline bool has_hidden_use (tree);
static inline void set_has_hidden_use (tree);
static inline tree parent_stmt (tree);
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.92
diff -c -p -r1.1.2.92 tree-ssa-ccp.c
*** tree-ssa-ccp.c 19 Sep 2003 12:08:47 -0000 1.1.2.92
--- tree-ssa-ccp.c 19 Sep 2003 16:56:38 -0000
*************** cfg_blocks_get ()
*** 1145,1164 ****
static void
add_var_to_ssa_edges_worklist (tree var)
{
! varray_type imm_uses = immediate_uses (SSA_NAME_DEF_STMT (var));
! if (imm_uses)
{
! unsigned int i;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (imm_uses); i++)
{
! tree use = VARRAY_TREE (imm_uses, i);
!
! if (stmt_ann (use)->in_ccp_worklist == 0)
! {
! stmt_ann (use)->in_ccp_worklist = 1;
! VARRAY_PUSH_TREE (ssa_edges, use);
! }
}
}
}
--- 1145,1163 ----
static void
add_var_to_ssa_edges_worklist (tree var)
{
! tree stmt = SSA_NAME_DEF_STMT (var);
! dataflow_t df = get_immediate_uses (stmt);
! int num_uses = num_immediate_uses (df);
! int i;
!
! for (i = 0; i < num_uses; i++)
{
! tree use = immediate_use (df, i);
! if (stmt_ann (use)->in_ccp_worklist == 0)
{
! stmt_ann (use)->in_ccp_worklist = 1;
! VARRAY_PUSH_TREE (ssa_edges, use);
}
}
}