<div dir="ltr"><div><div>I would consider putting all the data tables in a new section in the compiled binary. After runtime linking, you can then enumerate through all the tables in this section and sort them. You can then write a single istype function that performs a binary search at runtime.<br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, May 17, 2017 at 7:21 AM, Sanjoy Das via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Benoit,<br>
<br>
This is slightly off topic for the list, but have you checked to see<br>
if "Fast Subtype Checking in the HotSpot JVM" by Cliff Click and John<br>
Rose applies to your use case?<br>
<br>
-- Sanjoy<br>
<br>
On Tue, May 16, 2017 at 2:33 PM, Benoit Vey via llvm-dev<br>
<div class="HOEnZb"><div class="h5"><<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
> Thanks everyone for your answers.<br>
><br>
> Mats, my goal is do an alternate implementation of the subtyping test in the<br>
> Pony compiler. I'll try to keep the explanation short to avoid cluttering<br>
> the mail with irrelevant information.<br>
><br>
> Every object in Pony has a type descriptor, which is used in the subtyping<br>
> test to determine the real type of an object. The current algorithm is<br>
> suboptimal and we're trying out various alternatives. The full details are<br>
> on this github pull request: <a href="https://github.com/ponylang/ponyc/pull/1752" rel="noreferrer" target="_blank">https://github.com/ponylang/<wbr>ponyc/pull/1752</a><br>
><br>
> One of the alternatives, described by Sylvan Clebsch in the 6th message on<br>
> the PR, would involve looking at whether the type descriptor of an object<br>
> with an abstract type is the same as one of the subtypes of the abstract<br>
> type being tested. Here's an equivalent C code from the github PR:<br>
><br>
> bool SomeTraitTypeName__istype(<wbr>pony_type_t* desc)<br>
> {<br>
> switch((uintptr_t)desc)<br>
> {<br>
> case 0x878AB00:<br>
> case 0x878AB08:<br>
> case 0x878AB16:<br>
> case 0x878AC00:<br>
> case 0x878AC08:<br>
> case 0x878AD00:<br>
> return true;<br>
><br>
> default: {}<br>
> }<br>
><br>
> return false;<br>
> }<br>
><br>
> Since this can be implemented with either a switch or an if/else sequence, I<br>
> think I'll simply do the if/else instead.<br>
><br>
> mats petersson <<a href="mailto:mats@planetcatfish.com">mats@planetcatfish.com</a>> a écrit :<br>
><br>
><br>
>> On 15 May 2017 at 17:29, Benoit Vey via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
>> wrote:<br>
>><br>
>>> Hi.<br>
>>><br>
>>> First of all, some context. I'm trying to implement a new functionality<br>
>>> in<br>
>>> an LLVM-based compiler and I need to take various actions based on the<br>
>>> value of a given pointer, the possible values being the addresses of<br>
>>> various global constants. I tried to use a `switch` instruction but I<br>
>>> encountered several problems.<br>
>>><br>
>>> The "ideal switch" I'd like to have would look something like this (with<br>
>>> way more cases):<br>
>>><br>
>>> ; ModuleID = 'module'<br>
>>> source_filename = "module"<br>
>>><br>
>>> @var0 = global i32 0<br>
>>> @var1 = global i32 0<br>
>>><br>
>>> define i32 @func(i32*) {<br>
>>> entry:<br>
>>> switch i32* %0, label %unreachable [<br>
>>> i32* @var0, label %var0<br>
>>> i32* @var1, label %var1<br>
>>> ]<br>
>>><br>
>>> var0: ; preds = %entry<br>
>>> br label %post<br>
>>><br>
>>> var1: ; preds = %entry<br>
>>> br label %post<br>
>>><br>
>>> unreachable: ; preds = %entry<br>
>>> unreachable<br>
>>><br>
>>> post: ; preds = %var1,<br>
>>> %var0<br>
>>> %1 = phi i32 [ 0, %var0 ], [ 1, %var1 ]<br>
>>> ret i32 %1<br>
>>> }<br>
>>><br>
>>> This example is impossible because a `switch` cannot have pointer<br>
>>> operands. So I tried with `ptrtoint`, turning the `switch` into this:<br>
>>><br>
>>> %1 = ptrtoint i32* %0 to i64<br>
>>> switch i64 %1, label %unreachable [<br>
>>> i64 ptrtoint (i32* @var0 to i64), label %var0<br>
>>> i64 ptrtoint (i32* @var1 to i64), label %var1<br>
>>> ]<br>
>>><br>
>>> I'm a bit baffled by that one. According to the documentation the address<br>
>>> of a global value is a constant, yet this `switch` is impossible because<br>
>>> the result of the `ptrtoint` isn't a constant integer.<br>
>>><br>
>>> At that point, I don't really know how to proceed. My questions are:<br>
>>><br>
>>> - Why is `switch` restricted to integers?<br>
>>> - What is the result of a constant `ptrtoint` and why isn't it a constant<br>
>>> integer?<br>
>>> - Is there a way to switch on pointers despite these restrictions?<br>
>>><br>
>>> Thanks.<br>
>>><br>
>>> ------------------------------<wbr>------------------------------<wbr>----<br>
>>> This message was sent using IMP, the Internet Messaging Program.<br>
>>><br>
>>><br>
>>> ______________________________<wbr>_________________<br>
>>> LLVM Developers mailing list<br>
>>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>>><br>
>><br>
>> Aside from the obvious answer of "the switch needs compile time constants"<br>
>> (what I call "true constants" - they are constants that the LLVM compiler<br>
>> knows the actual value of, not constants as in "won't change during the<br>
>> execution of the program", such as variable and function addresses), it<br>
>> should be noted that unless the compiler & linker can be certain that for<br>
>> example the var0 and var1 address are "next to each other", this sort of<br>
>> construct will not benefit from any "switch" optimisation, it will be<br>
>> exactly like a switch with large, non-close values: an if/else if/else ...<br>
>> chain - probably not even able to do any cleverness of building a tree of<br>
>> which comes first [in a generic case of this, at the very least]. So if<br>
>> you<br>
>> have a case where you need to resolve a language construct where you can<br>
>> switch on a reference to a variable referring to a particular variable,<br>
>> then you probably have to make it into a compare + branch - or perhaps<br>
>> have<br>
>> a table and iterate over the choices. Even if LLVM knew how to do this, it<br>
>> wouldn't be possible to produce anything noticeably better [at least I<br>
>> can't think of anything - if anyone has some clever ways to solve this<br>
>> kind<br>
>> of problem, I would appreciate a comment...]<br>
>><br>
>> I still would like to hear from Benoit as to what the goal is here. I'm<br>
>> only guessing that it's a language where you can do something like "ref =<br>
>> var0; ... switch(ref) case var0: ... ; case var1: ... " or some such. Not<br>
>> that I know for sure what language that is.<br>
>><br>
>> --<br>
>> Mats<br>
>><br>
><br>
><br>
><br>
> ------------------------------<wbr>------------------------------<wbr>----<br>
> This message was sent using IMP, the Internet Messaging Program.<br>
><br>
><br>
> ______________________________<wbr>_________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div>