This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: 100x -O0 Compile Time Regression {3.2,3.3} -> {3.4,3.5}


> >Daniel, could you please also measure compile time on some less
> >artificial examples than 20001226-1.c before commiting this patch?  It
> >adds one unnecessary recount of whole dominator tree, so it might
> >be that it would not be win on usual functions not countaining 
> >thousands
> >of critical edges.
> I thought about this before "submitting" the patch.
> as Jeff pointed out, "et_splay with a whopping 27% of all the events 
> within cc1 (cc1 has just over 40% of the total events during make-k 
> check run)".
> Even on "more normal" cases, it can take up a significant amount of 
> time, because we perform the recount every time we split an edge (which 
> can happen any number of times during splitting critical edges).  
> That's obviously quadratic in the number of split edges.
> The only cases where the "submitted" version could a lose is where we 
> didn't *actually* need to recompute the dominators (because we didn't 
> split an edge).  I can take care of this if it's actually a time sink.

no -- we do not do full recounting of dominance information in
split_edge!  It is actually trivial to do the update, the only problem
is that the way it is done currently, it takes linear time in the number
of predecessors of the target vertex of the split edge.  This only
becomes a problem if you have a basic block with large indegree and
most of the incoming edges are critical, which does not usually happen
(other than in artificial testcases).

I have posted the patch that fixes it (by making it work in constant
time in the overhelming majority of cases).


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]