<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div><div><div>Hi DeLesley,</div><div><br></div><div>This is by design. LLVM's type system is very low-level; it doesn't even have a concept of types as most languages reason about them. For instance:</div><div><br></div></div><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; ">struct ColorRGB { float r, g, b; }</blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; ">struct ColorHSV { float h, s, v; }</blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; ">struct ColorHSV { float h, s, v; }</blockquote><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; ">struct Point3D { float x, y, z; }</blockquote><div><div><br></div><div>all become the same type { float, float, float } in LLVM IR, as you know. Expecting it to directly support generics seems a third-order-of-magnitude leap of faith. :) But there is good news for the faithful…</div><br><blockquote type="cite"></blockquote></div><div><br></div><div>In regards instantiation on demand, you can do this today:</div><div><br></div><div> 1. Create a facility such that you can determine which type-generic function x specialized types to instantiate based upon a symbol name. This could be a registry or a name mangling scheme.</div><div> 2. Implement your own ModuleProvider, overriding materializeFunction to perform specialization rather than loading the type from disk.</div><div><br></div><div><a href="http://llvm.org/doxygen/classllvm_1_1ModuleProvider.html">http://llvm.org/doxygen/classllvm_1_1ModuleProvider.html</a></div><div><br></div><div>You'll be in complete control of which insantiation, of course.</div><div><br></div><div><br></div><div><div><div><div>One could argue that LLVM could have much better support for type genericity by simply allowing full use of abstract data types (those containing opaque types) to be valid in IR, but not for codegen. In general, this creates a second-class "abstract function." The consequences of this would then need to ripple through the design. I wouldn't expect the impact to be too high, for the most part; LLVM already deals with objects of unknown size.</div><div><br></div><div>Still, there are a large number of potential foibles here. For instance, passing an argument can require platform-specific contortions to conform to the platform ABI, and these contortions depend on information from the high-level (C) type which is not recoverable from LLVM's structural types.</div><div><br></div><div>Specialization in this scheme would entail a modification of the existing CloneFunction algorithm. The method Type::refineAbstractTypeTo is not useful here, because it would destroy the original type-generic template.</div><div><div><br></div></div></div></div></div><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "><a href="http://llvm.org/doxygen/namespacellvm.html#82ca1ea30b8e181ed30dc10bdd1bfbad">http://llvm.org/doxygen/namespacellvm.html#82ca1ea30b8e181ed30dc10bdd1bfbad</a></blockquote><div><div><div><div><div><br></div><div>Instead of creating a literal copy, the algorithm would need to inspect the type of each IR object, replacing abstract data types (as LLVM already supports) with concrete ones as required by the instantiation. It could also jump through platform ABI hoops at call sites if required, but that would be quite complex.</div><div><br></div><div><div>But were I you, I wouldn't hold my breath waiting for someone else to implement it for me. :)</div><div><br></div><div>The answer <i>today</i> is to generate IR anew for each specialization, using the materializeFunction in a managed VM environment, or doing so statically. Improved support for specialization would be an interesting capability to add to LLVM's toolbox, but I would not expect LLVM to fully internalize support for one particular instantiation type system and scheme anytime in the foreseeable future.</div><div><br></div><div><br></div><div></div></div></div></div></div></div><div>As for code bloat, you could take .NET's compromise example and use the same code instantiation (but different metadata in your VM) for reference types, but create full specializations for value types. Given your concerns, you clearly have strong ideas about how type specialization should be implemented; why do you think having LLVM make the decision for you internally would be better than making the decision yourself, as you can do today?</div><div><div><br></div><div><br></div><div>I'll let others comment on the alternate type system. I wouldn't expect this to happen, personally.</div></div></div></div><div><div><div><div><div><br></div></div></div><blockquote type="cite"></blockquote></div><div><br></div><div>On 2009-02-17, at 12:26, DeLesley SpamBox wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>I'm a newcomer to llvm, but what you've done so far is very impressive.<br>Llvm is a godsend to anybody who is attempting to implement their own<br>their own language. :-) My company is considering using llvm as the<br>backend for a small matlab-like language for scientific computation; our<br>other option is MSIL.<br><br>After reading through the documentation, I noticed that llvm seems to<br>have one major limitation -- the lack of parametric polymorphism.</div></blockquote><div><br></div></div><div><blockquote type="cite"><div>I would<br>like to compile code such as the following:<br><br>max <T extends Comparable>(T a, T b) {<br> if (a > b) return a; else return b;<br>}<br><br>There are, of course, various ways to implement the above code. I could<br>compile the above function to a fully generic version with boxed arguments,<br>but that is very slow for scalar types. I could also take the C++ template<br>route, and generate different IR code for every type instantiation. However,<br>I have spent way too much time fighting with templates and code bloat to<br>like that idea.<br></div></blockquote><div><br></div><blockquote type="cite"><div>I believe that type instantiation should ideally be handled by llvm, rather<br>than the high-level language.</div></blockquote><div><br></div><blockquote type="cite"><div> First of all, there are a lot of<br>optimization passes<br>that are type-invariant; it would be nice to be able to partially<br>optimize the code<br>before instantiation. Second, type substitution is very similar to many of the<br>other optimizations that llvm already does, such as inlining, constant<br>propagation, and so on.</div></blockquote><div><br></div><blockquote type="cite"><div>And third, I am planning to use llvm in JIT mode, and<br>it just makes more sense (to me) to instantiate such functions on demand, at<br>run-time.<br></div></blockquote><div><br></div><blockquote type="cite"><div>Are there any plans to add such capability to llvm? I tried looking through the<br>list archives for any discussion, but the archives are not searchable (or I have<br>not figured out how to search them) so I didn't find much; feel free<br>to point me<br>to the proper place.</div></blockquote><blockquote type="cite"><div><br>How difficult would it be to add such a capability to llvm? I was thinking of<br>marking type variables like T as opaque types for the initial codegen, and then<br>writing a custom pass that instantiates them to real types. However, I don't<br>know if that would confuse or break other parts of the compiler infrastructure;<br>parametric polymorphism is not necessarily a trivial modification.<br><br>My personal background is in type theory; I received my doctorate from the<br>functional programming group at the University of Edinburgh. I love the fact<br>that llvm uses a typed assembly language, but the actual type system that<br>is currently used is pretty limited; it seems to be mostly a copy of C.<br><br>I know that compatibility with C is very important to llvm for obvious reasons,<br>but IMHO, the single biggest problem in making different languages talk to<br>one another is the type system. I'm not a fan of Microsoft's common type<br>system because it's far too OOP-centric, but the basic idea is a good one.<br>I think llvm would really benefit from having a much stronger, but<br>still low-level<br>and language-neutral type theory; it would enable cross-platform multi-language<br>libraries to be developed in any language, and then distributed as llvm IR.<br>(The other major necessity is an accurate and high-performance garbage<br>collector, but the intrinsics for that are already in place.)<br><br>Is anyone on this list familiar with System F, System F_sub, or System<br>F^\omega_sub? They comprise the basic, standard theories of parametric<br>polymorphism used in the academic world, and have been around for about<br>20 years. You can obviously get more sophisticated, but the System-F series<br>of calculi have the advantage that they are simple, well-known, off-the-shelf<br>solutions. Pick one, plug it into llvm, and you have a type system that can<br>compete with the JVM or .NET in terms of functionality, without being OOP<br>centric or sacrificing language neutrality. (System F is low-level --<br>OOP can be<br>easily implemented on top of it).<br></div></blockquote></div><div apple-content-edited="true"><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><br class="Apple-interchange-newline"><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div><br class="khtml-block-placeholder"></div>— Gordon<br class="Apple-interchange-newline"></span></span></span></span></span></div></span> </div><br></body></html>