Re: Is libiberty's splay-tree.c really a splay tree?
Michael Matz writes: >> > There were other people pointing out issues with the splay tree (but >> > all w/o copyright assignment and much larger patches). >> > >> > I know I did the last re-write of this piece of code but it's been a >> > long time ... in any case, previous reports were that the current >> > implementation degenerates in some cases. >> >> And I also distinctly remember some actual measurements where our >> current non-splay-tree is faster for a bootstrap (or similar testcases) >> than a real splay tree. Couple years ago, on this list. > > Referenced from: > http://gcc.gnu.org/ml/gcc/2006-10/msg00616.html Thanks. I knew I must be missing something. I can't explain why I didn't notice that when searching... > Basically the reimplementation of richi (r106584) improved on the > benchmarks (the former implementation was fairly bogus). The one from > Brian Makin with some changes by Ian Barnes was only slightly better (and > without copyright assignment). > > So it's very well possible that Richi doesn't rotate in optimal order. I > think it's harmless for the average O(log n) invariants of a splay tree. > Try some benchmarks :) Nah. Now I know the reason, I'm happy. :-) FWIW, the reason I asked was because I'm using a splay tree in a patch that I hope to send soon. The libiberty structures are a bit heavyweight, with the hooks stored alongside the root pointer, and with each node being a separate structure from the key and value. Since all I needed was a find-or-insert operation, I thought it would be OK to have a splay function in the pass itself. The justification was going to be that splaying is a fairly short textbook algorithm. Then I realised that we don't actually implement the libiberty one in what I thought was the textbook way. I'll have another look at whether I can reuse the libiberty code without bloating things too much. If not, I might just copy the algorithm we use there. Richard
Re: Is libiberty's splay-tree.c really a splay tree?
Hi, On Tue, 5 Jul 2011, Richard Sandiford wrote: > FWIW, the reason I asked was because I'm using a splay tree in a patch > that I hope to send soon. The libiberty structures are a bit heavyweight, > with the hooks stored alongside the root pointer, and with each node > being a separate structure from the key and value. Since all I needed > was a find-or-insert operation, find-and-insert only? Then a hashtable most probably is better anyway. Ciao, Michael.
[google] Last 4.6 merge google/main -> google/gcc-4_6
This is the last merge from google/main into google/gcc-4_6 (rev 175816). After this merge, both google/integration and google/main will resume tracking trunk. From now on, any changes needed from trunk or any other google branch, will need to be backported to google/gcc-4_6. Merges from gcc-4_6-branch will continue. Diego.
Re: Is libiberty's splay-tree.c really a splay tree?
Michael Matz writes: > On Tue, 5 Jul 2011, Richard Sandiford wrote: >> FWIW, the reason I asked was because I'm using a splay tree in a patch >> that I hope to send soon. The libiberty structures are a bit heavyweight, >> with the hooks stored alongside the root pointer, and with each node >> being a separate structure from the key and value. Since all I needed >> was a find-or-insert operation, > > find-and-insert only? Then a hashtable most probably is better anyway. Maybe. I was interested in using a splay tree because the pass tends to reference the most recently-added elements (the last handful rather than the last one). Richard
Added more notes and group picture to GCC gathering wiki
FYI. I added some more slides and a group picture to http://gcc.gnu.org/wiki/GCCGathering2011 Diego.
[pph] Merged trunk -> pph
This merge brings the pph branch up to rev 175832. No new failures nor merge conflicts this time. Tested on x86_64. Diego.
Re: GSOC - Student Roundup
Hi Philip, thanks for writing your experiences, I found it very useful. I certainly like the idea of having such a thread every once in a while, just to keep everyone updated about our projects. I'm also curious to learn about the experiences of other students that are writing code for GCC for the first time. Here goes mine: I am Dimitrios Apostolou (jimis on IRC) and I live in Heraklion-Crete, Greece. My project concerns making GCC leaner and faster. Reading GCC codebase has been a hard exercise for me. In fact it's the only project I know of that becomes more and more difficult as time passes... I will try to describe some of the major hurdles I've faced so far. I started by profiling the execution of cc1, the C compiler. In general I could find no big hot-spot, it was in good shape, but I could see 3-4 areas that could make some difference if improved (for example hash tables, assembly output, C parser, bitmaps). But diving in and trying to change things is a completely different story. Minor tweaks are easy to make, but usually have minor impact. If you want to see bigger speedup you have to break the interface of functions being used in hundreds of places, and that is hard. Sometimes it was impossible for me, I was getting crashes in places far away of code I had changed, so I ended up reverting to original versions. Spending some time with a specific part of GCC's codebase gives you the ability to dive deeper and work more efficiently. But that is the point when I usually have achieved something and I must move on to some other part. And the whole GCC codebase is so huge, that understanding one part means nothing when you move to another. My advice here is that if your project permits that, touch as little code as possible in GCC, and be really proficient with that. Treat the rest as a black box, or you'll spend too much time trying to understand everything. Another hurdle is the usage of too many macros. Even if they exist for making the code easier to read, I can't see how they achieve this in a few extreme cases. I have had gdb expand 20 full-lines macros on a wide screen. Plus the profiler can't actually profile code in macros, so the impact of some data structures in performance is hidden that way. My moments of greatest awe/horror so far have been while changing things in vectors (vec.[ch]), which is actually a fully templated structure implemented in CPP! Finally I believe that some parts of the compiler should have a big NO-ENTRY flag for beginners. In my case, after having improved little stuff in assembly output and hash tables, I decided -driven by profiler's output- to try improving things in dataflow analysis part of GCC. It's true that there is much to be improved there but it requires a good understanding of this complex part. Three weeks later I am still striving to change simple stuff and jump to the next part, but regressions I've introduced don't allow me to do so yet. The level of my understanding of this part is still basic, I've now only scratched the surface of Dataflow Analysis. If I had this knowledge in the beginning I'd probably leave that part for the end of the summer, if at all. My plans included visiting IRA (register allocator) next, but I think I'll skip directly to the c-parser which I understand more. These are my major difficulties with GCC, I'm curious to learn about other students experience so far. Of course don't get the wrong impression, my general feeling on GCC development is positive, the community is helpful and really friendly inspite of my daily spamming on the IRC. :-p In the end I feel the fact that GCC is a multi-headed monster makes it even more exciting to try and tame it. Good luck in everyone's project, Dimitris
Re: Long paths with ../../../../ throughout
Jon Grant writes: > Ian Lance Taylor wrote, On 03/07/11 05:27: >> Jon Grant writes: > [.] >>> Another reply for this old thread. I wondered, if collect2 is >>> possibly not needed in normal use on GNU/Linux, could GCC be >>> configured to call ld directly in those cases to save launching >>> another binary. >> >> collect2 is needed if you use -frepo or -flto. > > Hi Ian. > > Not sure how easy this is, but could those options simply be checked > to determine if the linker could be called directly? Would save > launching collect2 then, to speed up builds a bit! Sure, that seems feasible. Want to try to tackle it? Ian
[google] Merged gcc-4_6-branch into google/gcc-4_6
This brings google/gcc-4_6 up to rev 175849. Diego.
Re: GSOC - Student Roundup
Hello Philip + Dimitrios Thanks for your posts. I am another GSOC student. I am working on the Fortran front-end of GCC (gfortran). Like most GFortran developers, my background is more in the natural sciences (astrophysics in my case) rather than computer science. My project is to help add coarray support for GFortran. Coarrays are a cool new feature in the Fortran 2008 standard that give Fortran native support for parallel programming (as opposed to using MPI or OpenMP). Scientific simulations (especially in parallel clusters) are the bread and butter of Fortran. Learning how GCC works has been difficult but rewarding. My work is split between the libgfortran library, which is straight forward enough, and the Fortran front-end, which at first looked like gobbledygook. Today I can actually understand most front-end functions when I read them, but it took a long time to get to this point. GCC has a scary learning curve. The libgfortran library is more forgiving for the beginner. We are using MPI as the backend to implement coarrays and I have very much enjoyed learning MPI. So far my contributions have been modest, but now that I've crossed much of the learning curve, I feel optimistic. To an extent the progress has to be a bit slow because we are looking at the new Fortran standard and thinking about the best way to add features. Cheers, Daniel. -- I'm not overweight, I'm undertall.
gcc-4.4-20110705 is now available
Snapshot gcc-4.4-20110705 is now available on ftp://gcc.gnu.org/pub/gcc/snapshots/4.4-20110705/ and on various mirrors, see http://gcc.gnu.org/mirrors.html for details. This snapshot has been generated from the GCC 4.4 SVN branch with the following options: svn://gcc.gnu.org/svn/gcc/branches/gcc-4_4-branch revision 175894 You'll find: gcc-4.4-20110705.tar.bz2 Complete GCC MD5=0c1e5a415091a8a4f092cbb63686e98a SHA1=ef54a3290315f87b897db66bca2b21c3f3941d69 Diffs from 4.4-20110628 are available in the diffs/ subdirectory. When a particular snapshot is ready for public consumption the LATEST-4.4 link is updated and a message is sent to the gcc list. Please do not use a snapshot before it has been announced that way.
Re: [rs6000] -mno-sched-prolog vs .debug_frame
On Fri, Jul 1, 2011 at 8:31 PM, Richard Henderson wrote: > The implementation of TARGET_SCHED_PROLOG is incompatible with > some coming changes to how dwarf2 cfi is to be generated. > > Some suggested solutions are: > > (1) Remove the option. Is it really that interesting > beyond -mno-sched-insns2? > > (2) Emit blockage insns at the end of the prologue > and the beginning of the epilogue. That'll prevent > the majority of the changes that scheduling could > introduce. > > (3) Emit the prologue and epilogue somewhere after > scheduling and before final. E.g. md_reorg. > > I'd be delighted if someone could actually implement one > of these changes at some point in the next week, but > failing that please weigh in on the preferred solution. As we discussed on IRC, (1) with and eventual implementation of (2) are okay. Thanks, David
[pph] Re-instantiating namespaces and symbols
Jason,
We are having several issues re-instantiating symbols and
namespaces from a pph image. We are not handling all the cases
and the contortions we are going through are getting increasingly
bizarre. Perhaps you could give us a few pointers?
When we write the contents of a header file into an image, we do
the following in pph_write_file_contents
(http://gcc.gnu.org/viewcvs/branches/pph/gcc/cp/pph-streamer-out.c?view=markup):
static void
pph_write_file_contents (pph_stream *stream, cpp_idents_used *idents_used)
{
pph_out_identifiers (stream, idents_used);
pph_out_scope_chain (stream, scope_chain, false);
if (flag_pph_dump_tree)
pph_dump_namespace (pph_logfile, global_namespace);
pph_out_tree (stream, keyed_classes, false);
pph_out_tree_vec (stream, unemitted_tinfo_decls, false);
pph_out_tree (stream, static_aggregates, false);
}
In pph_out_scope_chain, we simply pickle out the contents of
scope_chain->bindings.
When compiling the translation unit, we read and merge a pph
image in pph_read_file_contents
(http://gcc.gnu.org/viewcvs/branches/pph/gcc/cp/pph-streamer-in.c?view=markup).
When re-building scope_chain->bindings, we call pph_add_bindings,
which will add everything under the file's scope_chain->bindings
into the current translation unit global_namespace.
This is currently pretty hacky, we are calling some symbol
registration functions that I'm not sure are completely right.
So we have various assembly miscomparisons, strange duplicate
declaration errors and outright ICEs. The code currently does:
static void
pph_add_bindings_to_namespace (struct cp_binding_level *bl, tree ns)
{
tree t, chain;
/* The chains are built backwards (ref: add_decl_to_level),
reverse them before putting them back in. */
bl->names = nreverse (bl->names);
bl->namespaces = nreverse (bl->namespaces);
for (t = bl->names; t; t = chain)
{
/* Pushing a decl into a scope clobbers its DECL_CHAIN.
Preserve it. */
chain = DECL_CHAIN (t);
pushdecl_into_namespace (t, ns);
if (TREE_CODE (t) == VAR_DECL && TREE_STATIC (t) && !DECL_EXTERNAL (t))
varpool_finalize_decl (t);
}
for (t = bl->namespaces; t; t = chain)
{
/* Pushing a decl into a scope clobbers its DECL_CHAIN.
Preserve it. */
chain = DECL_CHAIN (t);
pushdecl_into_namespace (t, ns);
if (NAMESPACE_LEVEL (t))
pph_add_bindings_to_namespace (NAMESPACE_LEVEL (t), t);
}
}
and we call it with global_namespace the first time. The call to
pushdecl_into_namespace is mostly a wrapper around
pushdecl_with_scope:
tree
pushdecl_into_namespace (tree dcl, tree nsp)
{
tree ret;
/* FIXME pph: There might be a better way to do this... */
struct cp_binding_level *level = NAMESPACE_LEVEL (nsp);
tree saved = current_namespace;
current_namespace = nsp;
#if 0
ret = pushdecl_maybe_friend (dcl, /*is_friend=*/false);
#else
ret = pushdecl_with_scope (dcl, level, /*is_friend=*/false);
#endif
current_namespace = saved;
return ret;
}
I've been looking around in the parser, and it seems to use a
variety of different symbol registration routines. I think all
this reconstruction we are doing needs to be re-written, it is
quite hacky and incomplete.
Is there a canonical way that we should use to rebuild the
elements from scope_chain->bindings? Could we not simply add
them to the current translation unit's scope_chain->bindings
as-is, instead of doing all these pushdecl calls?
When we read the PPH file back in we do need to create varpool
entries for some symbols so they get processed by the callgraph,
but I'm not sure what's the best way to go about that.
Thanks. Diego.
Re: [pph] Re-instantiating namespaces and symbols
On 07/06/2011 12:34 AM, Diego Novillo wrote: Is there a canonical way that we should use to rebuild the elements from scope_chain->bindings? Could we not simply add them to the current translation unit's scope_chain->bindings as-is, instead of doing all these pushdecl calls? That would probably be better. pushdecl_with_scope assumes that the new binding will be the innermost one, which is likely to cause headaches for you. When we read the PPH file back in we do need to create varpool entries for some symbols so they get processed by the callgraph, but I'm not sure what's the best way to go about that. I'm not sure where they're normally created. Jason
