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