> I have to admit that i had not considered the issue of having the later > stages of compilation of one function feed into the early stages of > another. The problem with this is that it implies a serial ordering of > the compilation and that is not going to yield a usable system for > compiling very large programs.
Yes, this is why I wanted to bring this in. I am not expert for whole program register allocation, but my understanding is that it can really help, especially on machine like x86-64, where saving prologues/epilogues are relatively expensive. It seems to me that it can't scale to really big programs, but it don't have to if we subdivide the programs sanely (ie do equivalent of region based compilation for large function). As long as the calls crossing boundaries are not very frequent, we should be all happy. Vladimir, Andrew, I am sure you know a lot more about global RA. Is it resonable to expect that RA needs to propagate things just down in topological order and can we split the program to resonably sized chunks where the RA can be handled locally? RA is IMO similar case as some other less standard optimizations that hardly fit into the planned framework. Those don't need necesarily cope with RTL level of info. Some of struct-reorg transforms affecting both datastructures and algorithms, for instance, might be problem. In analyze first, do all modification later framework their changes to function bodies will tend to affect analysis of all other passes so we would end up with need to teach every pass about other passes summaries and wire in a lot of knowledge about pass ordering. In future it might be dificult to maintain in future 50 such passes doing complex things affecting analysis of each other before modification is applied. It seems clear that for programs in C++ and similar languages we will need more advanced IPA tricks that what is commonly done and understood today. Except for the RA, it seem that one can always argue case by case how individual transform can be implemented in the combination with other passes, but overall having in our plans place for "BIG IPA" for the true whole program things scalling to thousdands and millions of functions and "small IPA" for hady things on resonably sized regions of program (that is what fits in memory and we want to compile at one node) might make our life easier. I can quite imagine "BIG IPA" doing things like profile read/estimation, constant propagation, devirtualization, clonning, (partial) inlining, alias analysis, identifying of identical function bodies, splicing program to regions for local compilation. That is, say, about 10-20 passes where most of them are analysis or based mostly on copying code (clonning/inlining) that is easy to fit into the framework. "small IPA" can do messy things like changing datastructures that does not escape regions, perhaps more involved versions of the passes already done: after doing all the inlining and using IPA data programs tends to simplify a lot (several times for C++ as can be easilly seen with data from early inlining and late inlining). Re-doing more exact alias analysis or inlining or whatewer might be interesting then. During final compilation it can do IPA RA and related propagation of low level info we realize at RTL level. The big IPA/small IPA is however still compatible with what you propose. We just do same splicing at each node and handle the splices. > > One of the the things to consider on this issue is how many of these > feedbacks can actually be preanalyzed. Before I wrote the pure-const > ipa pass, we discovered if a function was pure or const in some late rtl > pass and only later functions (in the compilation order) were able to > take advantage of that fact. By determining this as an ipa pass, we > have completely removed that ordering dependency. I admit that others > dependencies will be harder, if not impossible, to accommodate, but we > may find that many are. There are many tings you can do in the early IPA as we do it now. The late bits IMO reduce to very low level stuff. I.e. 1) for RA it is good to know what the called function really clobbers and save only registers that are needed (that is very simple global RA). I would say it is quite clear we can't resonaly estimate this on the gimple level before inlining we see in early IPA. 2) on i386 and friends we propagate down the amount of stack alignment needed. On gimple level IPA we can probably look for leaf functions and look for largest data it operates on, but it is at least quite inexact. See stack_alignment_needed, preferred_stack_boundary code. 3) it was several times considered that on PIC i386 libraries (and all targets where loading of GOT pointer is expensive), we can make alternative entry points to functions that expect GOT pointer to be already initialized. All calls within current unit can go to the local pointer if the caller already initialized GOT. If course one of the entry points can be optimized out if not used at all. I used to have patch for this, but except for the ellimination of entry points it don't need much IPA propagation, just downard propagation 4) some of our stuff, like decision if function can throw are estimated at IPA level and later refined if optimization helps. Same would apply to pure functions too, but it is not done. 5) I think more examples can be found I am not say that all our code quality stands on the above tricks, but we should understand what we are giving up in our design and see if something is really imporant. I think that RA is only that truly matters but I might've easilly missed something. > > I also have to admit that i did not consider the placement of functions > when i came up with my sorting strategy. I admit that my first simple > trick will likely lead to a bad ordering of functions, but so will > producing a separate .o file for every function (unless we later have a > smart linker that can reorder the functions to get a good answer). I think that we need independent way to order function in the resulting binary anyway. Optimal code layout tends to be exact oposite of ordering we benefit from most during compiling. Gas support subsections and fragments that helps here and some other systems has reordring built into linker. At the moment we do just very trivial function reordering: costructors, cold and very hot functions each have separate subsection, so if the hot region of program is small we are just happy with this. Once whole program is in and this is interesting, I think we should consider linker support for this as done eslewhere unless we manage way to produce single big .s file where we can use GAS's fragments. > > However, my meta point still stands. There is some global deterministic > sorting that the cgraph analyzer can do that each processor, with no > additional coordination can deterministicly pick which functions to > compile in its own space. For instance, we can use the existing order > and just have each process divide that order in some standard way by N > and take the nth slice for itself. > > If you do this, you can then, at least locally within the cluster of > functions, allocated on a single processor, do many of the tricks that > you describe above. Yep, we seem to be in sync here ;) I am just not really big fan of idea that the optimization decisions will depend on number of CPUs user has used to compile program. I will need to think a bit on the distribution issues. While you are right that most of network filesystem will not bring the whole file when you read the initial summary, it seems to be that as a result of inlining decisions and program splitting we might end up reading significant portion of the object files densely enough so we will consume a lot of bandwidth. Also I don't see you by doing the splitting completely in isolation based only on knowledge on number of nodes and very inexact estimate of size of functions that might relate to compilation time, you can ballance the work so the nodes work for resonaly similar amount of time when the time depends on many factor including nonuniformity of hardware. However I fully agree that we need experimenting here: I don't see the decision on particular of those two models (ie fully centralised with shipping objects to nodes or fully decentralized with each node making all decision by its own) is significandly affecting any of very near steps in the overall LTO/IPA plan outline at wiki: it would be good to keep in mind in the serializing code that it might be used to serialize just portion of the program in memory that is probably all needed to implement the centralized scheme or something in between if we find it benefical. Honza
