This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Path to speed up flow_loop_tree_node_add
- To: pfeifer at dbai dot tuwien dot ac dot at (Gerald Pfeifer)
- Subject: Re: Path to speed up flow_loop_tree_node_add
- From: Brad Lucier <lucier at math dot purdue dot edu>
- Date: Sat, 12 Feb 2000 15:09:16 -0500 (EST)
- Cc: lucier at math dot purdue dot edu, gcc at gcc dot gnu dot org
Gerald:
It doesn't really help; the problem is in the dominators calculation:
Flat profile:
Each sample counts as 0.000976562 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
44.90 95.62 95.62 59615 1.60 1.60 sbitmap_intersection_of_preds
8.12 112.92 17.29 6596 2.62 2.62 flow_loop_exits_find
7.00 127.83 14.92 6596 2.26 2.26 flow_loop_pre_header_find
3.19 134.62 6.79 8 849.00 4333.99 jump_optimize_1
2.61 140.19 5.56 10438088 0.00 0.00 rtx_renumbered_equal_p
2.49 145.49 5.30 9123105 0.00 0.00 find_cross_jump
2.21 150.19 4.71 24702 0.19 0.19 delete_from_jump_chain
1.82 154.07 3.88 39230652 0.00 0.00 active_insn_p
1.25 156.74 2.67 70351 0.04 0.04 make_edge
1.03 158.93 2.19 149629 0.01 0.01 record_one_conflict
0.83 160.71 1.78 1 1775.39 212723.80 yyparse
-----------------------------------------------
0.07 96.34 3/3 flow_loops_find [7]
[8] 45.3 0.07 96.34 3 compute_flow_dominators [8]
95.62 0.01 59615/59615 sbitmap_intersection_of_preds [9]
0.60 0.00 59618/59618 sbitmap_a_and_b [111]
0.10 0.00 3/6 sbitmap_vector_alloc [209]
0.00 0.01 3/3 sbitmap_vector_zero [656]
0.00 0.00 3/3 sbitmap_vector_ones [749]
0.00 0.00 3/26511 sbitmap_zero [645]
0.00 0.00 3/202720 xmalloc [358]
-----------------------------------------------
95.62 0.01 59615/59615 compute_flow_dominators [8]
[9] 44.9 95.62 0.01 59615 sbitmap_intersection_of_preds [9]
0.01 0.00 59615/59615 sbitmap_copy [629]
-----------------------------------------------
Also, re submitting a rewrite of compute_flow_dominators,
I don't have an assignment on file with the FSF, and I hear that it
has been difficult in the past to get one from my employer (Purdue),
although it may be easier for me as a faculty member.
Brad
>
> On Sat, 12 Feb 2000, Michael Hayes wrote at gcc-patches:
> > This patch avoids the quadratic worst case performance of the previous
> > algorithm. OK to commit?
> >
> > Michael.
> >
> > 2000-02-12 Michael Hayes <m.hayes@elec.canterbury.ac.nz>
> >
> > * flow.c (flow_loop_tree_node_add): Use better algorithm by passing
> > previously inserted node instead of root node. Caller changed.
>
> Brad, it would be interesting to see how much this helps your code.
> (Jeff has already approved the patch.)
>
> Perhaps you could give it a trie and report to gcc@gcc.gnu.org?
>
> Gerald
> --
> Gerald "Jerry" pfeifer@dbai.tuwien.ac.at http://www.dbai.tuwien.ac.at/~pfeifer/
>