Re: switches in GCC JIT?

[David Malcolm <dmalcolm@redhat.com>]

On Tue, 2015-06-23 at 00:02 +0200, Basile Starynkevitch wrote:
> On 06/22/2015 11:42 PM, David Malcolm wrote:
> > On Mon, 2015-06-22 at 23:40 +0200, Basile Starynkevitch wrote:
> >> Hello David & all
> >>
> >> I'm guessing that GCCJIT is able to emit switch like statements, e.g.
> >> using GIMPLE_SWITCH statements
> >> internally.
> > No, it doesn't.
> >
> >> But I don't understand how is it possible. It looks like
> >> gimple_build_switch does not occur in gcc/jit/
> > Currently gcc/jit builds functions at the tree level and hands them off
> > to the gimplifier, so you wouldn't see that in any case.  (in theory it
> > could be ported to directly generate gimple).
> >
> >> Are switch statements omitted from GCCJIT?
> > Yes.
> >
> >> If yes, why???
> > I intentionally didn't implement them, to keep the API simpler.
> >
> > I've never run into a need for them when implementing jit-compilation,
> > and in theory they could be implemented using conditionals (albeit
> > without the nice optimizations that we have for lowering GIMPLE_SWITCH).
> >
> > There was some discussion about this here:
> >   https://gcc.gnu.org/ml/jit/2014-q4/msg00116.html
> >
> >> David, do you intend to improve that?
> > Do you have a use-case for them?  We can add them if we need them.
> 
> Any language (MELT, Ocaml, Haskell, ....) having some pattern matching 
> would use a lot of switches.
> Or most efficient implementations of Rete algorithm, or similar stuff 
> when compiling Prolog-like or CLIPS-like rules.
> 
> Also, translation of most finite state automatons is done by a switch 
> (often a quite big one, with one case per each state).
> 
> At last, any kind of "byte-code" interpreter uses switches.
> 
> And many languages have a switch like construct, that would be trivial 
> to translate to a GIMPLE_SWITCH, but painful to translate otherwise.
> 
> 
> All the bytecodes I know (e.g. JVM & Ocaml) have switch-like constructs, 
> and it would be easy to translate them to a GIMPLE_SWITCH, and painful 
> otherwise.

As it happens, none of the bytecode languages I've implemented so far
have switch-like constructs.

But I see now that the JVM has opcodes "lookupswitch" and "tableswitch";
those alone make a compelling case for libgccjit supporting switches.

I'm working on it now; the API I'm thinking of looks like this:

extern void
gcc_jit_block_end_with_switch (gcc_jit_block *block,
			          gcc_jit_location *loc,
			          gcc_jit_rvalue *expr,
			          gcc_jit_block *default_block,
			          int num_cases,
			          gcc_jit_rvalue **case_min_values,
			          gcc_jit_rvalue **case_max_values,
			          gcc_jit_block **case_blocks);


thus supporting ranged cases, whilst also allowing individual values, by
simply passing in the same table for both case_min_values and
case_max_values.

> BTW, if we don't have switches, we should at least have indirect jumps, 
> and the ability to retrieve, as a label, the starting address of any 
> basic block. (i.e. the equivalent of goto *ptr; and of &&label in C). If 
> that is possible today, we need more documentation about that (at least 
> saying that switch statements could be translated that way)
> 
> And of course, leveraging on all the important optimizations done by GCC 
> on GIMPLE_SWITCH is essential...
> 
> Actually, I'm surprised you are asking what is the use case for 
> switches. I feel they are obvious and numerous... I would be annoyed, 
> e.g. if I could not use switches in my C++ or C code. Replacing a switch 
> with a sequence of if is an annoyance, and is probably a major 
> performance loss (unless GCC optimizations are clever enough to replace 
> them with a switch; which might sometimes be true, but not always).