Ben: I've changed subject. This discussion is important, but I suspect it isn't helping Jeremie much.
On Fri, Apr 8, 2011 at 2:39 PM, Ben Karel <[email protected]> wrote: > On Fri, Apr 8, 2011 at 4:31 AM, Jonathan S. Shapiro <[email protected]>wrote: > > > Could you give a concrete example of an LLVM optimization pass that >> destroys type information in a way that undermines GC? I'd like to >> experiment with my LLVM-based GC and see if it breaks! >> > Ben: I think I let a rant take over inappropriately. I did, at least, acknowledge that I haven't looked at LLVM internals in a while, and that things may well have improved. Back when I last looked, the GCREAD/GCWRITE intrinsics did not exist yet. What I *can* do is give you an example of a classic optimization that (a) is necessary, but (b) in typical form makes a mess for GC. Consider optimizing something that uses the DOACROSS pattern. In a typical (GC oblivious) optimizer, you apply a combination of unrolling, strength reduction, and partial evaluation to eliminate register pressure. A very common result of this is that array/vector base pointer registers get merged with the indexing offset registers into a single pointer that is used to index into the middle of the array/vector. In the worst case the resulting "indexing" pointer can end up past the end of the array/vector and a negative offset can end up getting used. You're probably aware that Boehm has a big ugly mechanism to deal with such "interior" pointers, and that their solution is basically a hack. They rely (tacitly) on the fact that the same optimization is not, in practice, applied to structure offsets - which is rare in practice, but does in fact happen sometimes. Now we don't want to eliminate this optimization. What we want is for the optimization phase to emit information that either (a) preserves the base pointer somewhere and identifies these combination values as offsets relative to that base - and then makes that info part of the register map, or (b) provides an algorithm by which the collector can re-derive the base pointer at runtime, or (c) at least clearly identifies the register as "likely interior", and restricts the use of interior pointers to cases that are known (by the optimizer) to be supported by the runtime. This particular example is so universal and so important that I would be surprised if LLVM does not contain it. If you happen to know what they do in this case, and how they avoid boogering a relocating collector, I'ld be very interested to hear about it. In any case, it's an example of the kind of thing where an optimization pass written by someone who is thinking in terms of non-managed source languages will be written in such a way that you end up re-writing the pass when you have to accommodate the new case. We are then presented with the difficulty of designing test cases that will let us determine which passes are currently "relocating GC safe" and which passes are not. > > It's also worth noting that there are neither required nor default > optimization passes, at either the LLVM or MC levels. It's all opt-in... > I agree, but ultimately that is a cop-out. The point of going to LLVM is that we get to take advantage existing infrastructure. If we are forced to turn the existing infrastructure off, then what's the point of using LLVM. I do understand that it isn't that black and white, but you see my point. > Absolutely. And in the absence of a compiler that preserves the necessary >> information across phases, there is absolutely no point trying to deploy any >> of the good - or even moderately good - GC strategies. >> > > Could you summarize what information LLVM currently loses in practice, in > what phases? > No - again because I'm not current on the infrastructure. But consider the example I gave above. The practical approach is probably (a), but you need to make sure that "derived register" relationships are preserved by subsequent passes as they do (e.g.) CSE, partial evaluation, and so forth. That's one reason why it's useful to have types in your front-end -- the > address space as a whole may be heterogeneous, but types can show that > subsets of the address space are entirely under the control of the language > runtime. That guarantee is modulo intentional or unintentional twiddling > from external sources, but if you don't have that guarantee, you're screwed > on correctness, not just performance. > That's one reason. Another is that type preservation serves as a very strong sanity check on the passes of the compiler. But I think you're making an assumption here that I do not share. In the long term, I think we either need to be thinking in terms of moving C/C++/Fortran code into the GC world, or we need to be thinking in terms of automated conversion. The "arms length" approach doesn't scale well, and the state of the runtime heap is too fragile a thing to leave in the hands of programmers if you don't check what they did. > Custom GC effectively means control over custom allocators. Isn't one of > the main points of BitC, and Cyclone, that fine-grained control over memory > is important for performance? > No. Fine-grained control over *layout*, yes. Fine-grained control over *allocation*, not in general. > Compiler infrastructures take a long time to build, and are long term >>> investments. They involve core technical decisions that are *very* difficult >>> to change (e.g. the IR design). For this reason, successful compiler >>> infrastructures simply cannot afford to succumb to ... short-term thinking >>> ... >>> >> > I think you're not giving the LLVM team enough credit for their capacity to > evolve their infrastructure if they see the need. > Actually, that's not it. Having run one commercial ground-up compiler group and worked closely with two others, I think that I have a pretty clear handle on the risks and costs here. Having said that, Chris is a very smart guy, so maybe he will find a way. > Could you explicate what you perceive to be the fundamental design flaws, > and how the LLVM IR needs to be changed? > I can't even say if it's a matter for IR changes. But if they want to do GC'd languages well, they need a definition of constitutes well-formed input/output from a pass, and what constraints must be maintained in the transformation process in order to preserve GC support. I find the LLVM infrastructure to be a disappointment from this perspective. >> Given how recently it was designed, and the clearly desperate need to deal >> with mixing managed and non-managed languages, the decision to omit core >> support for managed languages from the LLVM design strikes me as a bad >> design decision. Micrsoft has definitely gotten this right; I think Apple >> has not. The decision to *implement *LLVM in a non-managed language also >> strikes me as ill chosen, though that decision more sense to me >> situationally. >> > > Let he who is without sin cast the first stone, eh? :-) > Fair enough, but there is an important difference. The decision to implement LLVM in C++ was intended from the start to be permanent. The decision to implement BitC in C++ was intended from the start to be thrown away as fast as we possibly could. In fact, we only fell back to that approach after finding that we could not effectively implement in the more suitable languages that were only just emerging at the time. If there had been a viable C# implementation on Linux in 2004, I would have used it. This is why I noted that Chris's implementation choice makes sense to me situationally. And you'll note that we *never* attempted an implementation that relied on manual memory management. But the permanent vs. transitional distinction is quite real. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
