Hit a showstopper issue

Hit a showstopper issue

[Dibyendu Majumdar]

I have hit an issue that is a show stopper for me.

In Lua, redundant bytecodes are emitted that end up being unreachable
blocks in the generated code. In LLVM these unreachable blocks are
simply eliminated during optimization. But libgccjit is failing with
an error.

Here is a minimal Lua function.

x=function() return; end

The generated Lua bytecode is this:

function <test.lua:1,1> (2 instructions at 0xad4840)
0 params, 2 slots, 0 upvalues, 0 locals, 0 constants, 0 functions
1 [1] RETURN   0 1
2 [1] RETURN   0 1
constants (0) for 0xad4840:
locals (0) for 0xad4840:
upvalues (0) for 0xad4840:

As you can see there is a redundant RETURN bytecode.

The code I generate is this:

static int
ravif1 (struct ravi_lua_State * L)
{
  struct ravi_TValue * base;

entry:
  base = L->ci->u.l.base;
  base = L->ci->u.l.base;
  L->top = &base[(int)0];
  if ((struct ravi_LClosure *)L->ci->func->p->sizep > (int)0) goto
<UNNAMED BLOCK 0x2360800>; else goto <UNNAMED BLOCK 0x2360850>;

<UNNAMED BLOCK 0x2360800>:
  (void)luaF_close (L, base);
  goto <UNNAMED BLOCK 0x2360850>;

<UNNAMED BLOCK 0x2360850>:
  (void)luaD_poscall (L, &base[(int)0]);
  return (int)1;

<UNNAMED BLOCK 0x2360c00>:
  base = L->ci->u.l.base;
  L->top = &base[(int)0];
  if ((struct ravi_LClosure *)L->ci->func->p->sizep > (int)0) goto
<UNNAMED BLOCK 0x2360a60>; else goto <UNNAMED BLOCK 0x2361290>;

<UNNAMED BLOCK 0x2360a60>:
  (void)luaF_close (L, base);
  goto <UNNAMED BLOCK 0x2361290>;

<UNNAMED BLOCK 0x2361290>:
  (void)luaD_poscall (L, &base[(int)0]);
  return (int)1;
}

When this is compiled the following errors occur:

libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad5c40>
libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad5aa0>
libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad62d0>

Re: Hit a showstopper issue

[Dibyendu Majumdar]

I worked around this by patching my copy of gcc 5.1 - basically
disabled the validation that checks for unreachable blocks.
After that and some bug fixes and workarounds (see next post) it seems to work!



On 14 June 2015 at 21:00, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> I have hit an issue that is a show stopper for me.
>
> In Lua, redundant bytecodes are emitted that end up being unreachable
> blocks in the generated code. In LLVM these unreachable blocks are
> simply eliminated during optimization. But libgccjit is failing with
> an error.
>
> Here is a minimal Lua function.
>
> x=function() return; end
>
> The generated Lua bytecode is this:
>
> function <test.lua:1,1> (2 instructions at 0xad4840)
> 0 params, 2 slots, 0 upvalues, 0 locals, 0 constants, 0 functions
> 1 [1] RETURN   0 1
> 2 [1] RETURN   0 1
> constants (0) for 0xad4840:
> locals (0) for 0xad4840:
> upvalues (0) for 0xad4840:
>
> As you can see there is a redundant RETURN bytecode.
>
> The code I generate is this:
>
> static int
> ravif1 (struct ravi_lua_State * L)
> {
>   struct ravi_TValue * base;
>
> entry:
>   base = L->ci->u.l.base;
>   base = L->ci->u.l.base;
>   L->top = &base[(int)0];
>   if ((struct ravi_LClosure *)L->ci->func->p->sizep > (int)0) goto
> <UNNAMED BLOCK 0x2360800>; else goto <UNNAMED BLOCK 0x2360850>;
>
> <UNNAMED BLOCK 0x2360800>:
>   (void)luaF_close (L, base);
>   goto <UNNAMED BLOCK 0x2360850>;
>
> <UNNAMED BLOCK 0x2360850>:
>   (void)luaD_poscall (L, &base[(int)0]);
>   return (int)1;
>
> <UNNAMED BLOCK 0x2360c00>:
>   base = L->ci->u.l.base;
>   L->top = &base[(int)0];
>   if ((struct ravi_LClosure *)L->ci->func->p->sizep > (int)0) goto
> <UNNAMED BLOCK 0x2360a60>; else goto <UNNAMED BLOCK 0x2361290>;
>
> <UNNAMED BLOCK 0x2360a60>:
>   (void)luaF_close (L, base);
>   goto <UNNAMED BLOCK 0x2361290>;
>
> <UNNAMED BLOCK 0x2361290>:
>   (void)luaD_poscall (L, &base[(int)0]);
>   return (int)1;
> }
>
> When this is compiled the following errors occur:
>
> libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad5c40>
> libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad5aa0>
> libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad62d0>

Re: Hit a showstopper issue

[David Malcolm]

On Sun, 2015-06-14 at 21:00 +0100, Dibyendu Majumdar wrote:
> I have hit an issue that is a show stopper for me.
> 
> In Lua, redundant bytecodes are emitted that end up being unreachable
> blocks in the generated code. In LLVM these unreachable blocks are
> simply eliminated during optimization. But libgccjit is failing with
> an error.
> 
> Here is a minimal Lua function.
> 
> x=function() return; end
> 
> The generated Lua bytecode is this:
> 
> function <test.lua:1,1> (2 instructions at 0xad4840)
> 0 params, 2 slots, 0 upvalues, 0 locals, 0 constants, 0 functions
> 1 [1] RETURN   0 1
> 2 [1] RETURN   0 1
> constants (0) for 0xad4840:
> locals (0) for 0xad4840:
> upvalues (0) for 0xad4840:
> 
> As you can see there is a redundant RETURN bytecode.
> 
> The code I generate is this:
> 
> static int
> ravif1 (struct ravi_lua_State * L)
> {
>   struct ravi_TValue * base;
> 
> entry:
>   base = L->ci->u.l.base;
>   base = L->ci->u.l.base;
>   L->top = &base[(int)0];
>   if ((struct ravi_LClosure *)L->ci->func->p->sizep > (int)0) goto
> <UNNAMED BLOCK 0x2360800>; else goto <UNNAMED BLOCK 0x2360850>;
> 
> <UNNAMED BLOCK 0x2360800>:
>   (void)luaF_close (L, base);
>   goto <UNNAMED BLOCK 0x2360850>;
> 
> <UNNAMED BLOCK 0x2360850>:
>   (void)luaD_poscall (L, &base[(int)0]);
>   return (int)1;
> 
> <UNNAMED BLOCK 0x2360c00>:
>   base = L->ci->u.l.base;
>   L->top = &base[(int)0];
>   if ((struct ravi_LClosure *)L->ci->func->p->sizep > (int)0) goto
> <UNNAMED BLOCK 0x2360a60>; else goto <UNNAMED BLOCK 0x2361290>;
> 
> <UNNAMED BLOCK 0x2360a60>:
>   (void)luaF_close (L, base);
>   goto <UNNAMED BLOCK 0x2361290>;
> 
> <UNNAMED BLOCK 0x2361290>:
>   (void)luaD_poscall (L, &base[(int)0]);
>   return (int)1;
> }
> 
> When this is compiled the following errors occur:
> 
> libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad5c40>
> libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad5aa0>
> libgccjit.so: error: unreachable block: <UNNAMED BLOCK 0xad62d0>

The idea of this check was an attempt to be helpful, in that in other
bytecode compilers I've worked on, an unreachable block meant a bug in
the compiler, and the check has helped me track down bugs in those.

Clearly this check is unhelpful for Lua, so maybe we need an option to
disable it, something like:
  GCC_JIT_BOOL_OPTION_ERROR_ON_UNREACHABLE_BLOCKS
or somesuch.

A (nasty) workaround might be to generate something like this:

   if (0)
     goto block0;
   else if (0)
     goto block1;
   ...
   else if (0)
     goto blockN;
   else
     goto the real block;

which after optimization is equivalent to just:

   goto the real block;

but which fools the check into thinking all blocks0..N are reachable
(yes, I said it was nasty...)

Sorry about this.

Dave

Re: Hit a showstopper issue

[Dibyendu Majumdar]

On 15 June 2015 at 01:51, David Malcolm <dmalcolm@redhat.com> wrote:
> On Sun, 2015-06-14 at 21:00 +0100, Dibyendu Majumdar wrote:
>> In Lua, redundant bytecodes are emitted that end up being unreachable
>> blocks in the generated code. In LLVM these unreachable blocks are
>> simply eliminated during optimization. But libgccjit is failing with
>> an error.
>
> The idea of this check was an attempt to be helpful, in that in other
> bytecode compilers I've worked on, an unreachable block meant a bug in
> the compiler, and the check has helped me track down bugs in those.
>
> Clearly this check is unhelpful for Lua, so maybe we need an option to
> disable it, something like:
>   GCC_JIT_BOOL_OPTION_ERROR_ON_UNREACHABLE_BLOCKS
> or somesuch.
>

Yes - although I am not sure of the value of this check as it is legal
to have unreachable blocks of code and I can think of scenarios where
they may be used deliberately - for instance what appears unreachable
may become reachable given coroutines and closures. An unreachable
piece of code may be a place holder for some future hot patch. Of
course in such cases the optimization must be disabled but the
decision should not be made by the JIT library.

I apologize for bringing in LLVM comparison again - but they have a
model that seems to work just right. Basically the LLVM
verifier/compiler will detect invalid blocks and conrol flow - which
is more important for debugging purposes. Usually a bug will manifest
itself in some corruption in the control flow - e.g. variable not
accessible in all code paths and such - LLVM detects these and raises
errors. I am not sure of the extent of the validation performed in
libgccjit - but perhaps if the validation was more extensive then that
would suffice?

In other words I am asking whether this option is actually a
workaround for lack of sufficient validation of the control flow?

Regards
Dibyendu

Re: Hit a showstopper issue

[Dibyendu Majumdar]

On 15 June 2015 at 20:32, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> I apologize for bringing in LLVM comparison again - but they have a
> model that seems to work just right. Basically the LLVM
> verifier/compiler will detect invalid blocks and conrol flow - which
> is more important for debugging purposes. Usually a bug will manifest
> itself in some corruption in the control flow - e.g. variable not
> accessible in all code paths and such - LLVM detects these and raises
> errors.

Of course LLVM's IR is SSA form so that probably makes it easier to
validate the control flow. They described this as 'well formed'-ness -
the verifier detects if the code is  well-formed and complains if 'the
definition of %x does not dominate all of its uses'. My understanding
is that the IR you are working with is not SSA-form so this type of
validation may not be possible...

In any case a warning about unreachable bocks may be more appropriate
than errors.

Regards

Re: Hit a showstopper issue

[David Malcolm]

On Mon, 2015-06-15 at 21:25 +0100, Dibyendu Majumdar wrote:
> On 15 June 2015 at 20:32, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> > I apologize for bringing in LLVM comparison again - but they have a
> > model that seems to work just right. Basically the LLVM
> > verifier/compiler will detect invalid blocks and conrol flow - which
> > is more important for debugging purposes. Usually a bug will manifest
> > itself in some corruption in the control flow - e.g. variable not
> > accessible in all code paths and such - LLVM detects these and raises
> > errors.
> 
> Of course LLVM's IR is SSA form so that probably makes it easier to
> validate the control flow. They described this as 'well formed'-ness -
> the verifier detects if the code is  well-formed and complains if 'the
> definition of %x does not dominate all of its uses'. My understanding
> is that the IR you are working with is not SSA-form so this type of
> validation may not be possible...

Yes: the IR exposed by the libgccjit API is not SSA-form.  The optimizer
does use SSA-form internally.

I think my opinion at the time was that forcing users to create phi
nodes was unnecessary work for them; let the API do it automatically,
internally.   I don't know if the loss of this kind of validation is a
show-stopper; it feels to me more like a fussy API that the user has to
do extra work to appease.  But I could be wrong.

> In any case a warning about unreachable bocks may be more appropriate
> than errors.

FWIW I've experimented in the past with turning on warnings about
uninitialized vars, so maybe we need an API setting for validations,
with each validation having a tri-state:
  * perform validation, as error
  * perform validate, as warnings to stderr
  * don't validate

(thinking aloud here)

Dave

Re: Hit a showstopper issue

[Dibyendu Majumdar]

On 15 June 2015 at 21:54, David Malcolm <dmalcolm@redhat.com> wrote:
> Yes: the IR exposed by the libgccjit API is not SSA-form.  The optimizer
> does use SSA-form internally.
>
> I think my opinion at the time was that forcing users to create phi
> nodes was unnecessary work for them; let the API do it automatically,
> internally.   I don't know if the loss of this kind of validation is a
> show-stopper; it feels to me more like a fussy API that the user has to
> do extra work to appease.  But I could be wrong.
>

In LLVM I hardly ever specify phi-nodes - it constructs them during
optimization when it detects a scenario requiring a phi-node. I just
declare my locals and use them appropriately - but yes one can
explicitly code phi-nodes and to me (who is not so familiar with the
concept) this is painful.

>> In any case a warning about unreachable bocks may be more appropriate
>> than errors.
>
> FWIW I've experimented in the past with turning on warnings about
> uninitialized vars, so maybe we need an API setting for validations,
> with each validation having a tri-state:
>   * perform validation, as error
>   * perform validate, as warnings to stderr
>   * don't validate
>

That makes sense.

Regards

Re: Hit a showstopper issue

[David Malcolm]

On Mon, 2015-06-15 at 22:18 +0100, Dibyendu Majumdar wrote:
> On 15 June 2015 at 21:54, David Malcolm <dmalcolm@redhat.com> wrote:
> > Yes: the IR exposed by the libgccjit API is not SSA-form.  The optimizer
> > does use SSA-form internally.
> >
> > I think my opinion at the time was that forcing users to create phi
> > nodes was unnecessary work for them; let the API do it automatically,
> > internally.   I don't know if the loss of this kind of validation is a
> > show-stopper; it feels to me more like a fussy API that the user has to
> > do extra work to appease.  But I could be wrong.
> >
> 
> In LLVM I hardly ever specify phi-nodes - it constructs them during
> optimization when it detects a scenario requiring a phi-node. I just
> declare my locals and use them appropriately - but yes one can
> explicitly code phi-nodes and to me (who is not so familiar with the
> concept) this is painful.
> 
> >> In any case a warning about unreachable bocks may be more appropriate
> >> than errors.
> >
> > FWIW I've experimented in the past with turning on warnings about
> > uninitialized vars, so maybe we need an API setting for validations,
> > with each validation having a tri-state:
> >   * perform validation, as error
> >   * perform validate, as warnings to stderr
> >   * don't validate

I'm thinking of something like this:

enum gcc_jit_validation_check
{
  GCC_JIT_VALIDATION_CHECK_UNREACHABLE_BLOCKS,
  GCC_JIT_VALIDATION_CHECK_UNINITIALIZED_LOCALS,

  GCC_JIT_NUM_VALIDATION_CHECKS
};

enum gcc_jit_validation_response
{
  GCC_JIT_VALIDATION_IGNORE,
  GCC_JIT_VALIDATION_LOG_TO_STDERR,
  GCC_JIT_VALIDATION_ERROR,

  GCC_JIT_NUM_VALIDATION_RESPONSES
};

extern void
gcc_jit_context_set_validation (gcc_jit_context *ctxt,
                                gcc_jit_validation_check check,
                                gcc_jit_validation_response response);

I'm not in love with any of the above names ("IGNORE" is really "don't
bother running this", it's not really a "response").

I wonder if there are any other existing gcc warnings that might be
useful to libgccjit users.  Thoughts?

Dave

Re: Hit a showstopper issue

[Dibyendu Majumdar]

On 16 June 2015 at 19:41, David Malcolm <dmalcolm@redhat.com> wrote:
>> >> In any case a warning about unreachable bocks may be more appropriate
>> >> than errors.
>> >
>> > FWIW I've experimented in the past with turning on warnings about
>> > uninitialized vars, so maybe we need an API setting for validations,
>> > with each validation having a tri-state:
>> >   * perform validation, as error
>> >   * perform validate, as warnings to stderr
>> >   * don't validate
>
> I'm thinking of something like this:
>
> enum gcc_jit_validation_check
> {
>   GCC_JIT_VALIDATION_CHECK_UNREACHABLE_BLOCKS,
>   GCC_JIT_VALIDATION_CHECK_UNINITIALIZED_LOCALS,
>
>   GCC_JIT_NUM_VALIDATION_CHECKS
> };

You could omit the word CHECK I think.

>
> enum gcc_jit_validation_response
> {
>   GCC_JIT_VALIDATION_IGNORE,
>   GCC_JIT_VALIDATION_LOG_TO_STDERR,
>   GCC_JIT_VALIDATION_ERROR,
>
>   GCC_JIT_NUM_VALIDATION_RESPONSES
> };
>
> extern void
> gcc_jit_context_set_validation (gcc_jit_context *ctxt,
>                                 gcc_jit_validation_check check,
>                                 gcc_jit_validation_response response);
>
> I'm not in love with any of the above names ("IGNORE" is really "don't
> bother running this", it's not really a "response").

How about DISABLE instead of IGNORE?


>
> I wonder if there are any other existing gcc warnings that might be
> useful to libgccjit users.  Thoughts?
>

This is an interesting question. The problem is without understanding
what is possible I am not sure I can answer.

Regards

Re: Hit a showstopper issue

[David Malcolm]

On Mon, 2015-06-15 at 16:54 -0400, David Malcolm wrote:
> On Mon, 2015-06-15 at 21:25 +0100, Dibyendu Majumdar wrote:
> > On 15 June 2015 at 20:32, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> > > I apologize for bringing in LLVM comparison again - but they have a
> > > model that seems to work just right. Basically the LLVM
> > > verifier/compiler will detect invalid blocks and conrol flow - which
> > > is more important for debugging purposes. Usually a bug will manifest
> > > itself in some corruption in the control flow - e.g. variable not
> > > accessible in all code paths and such - LLVM detects these and raises
> > > errors.
> > 
> > Of course LLVM's IR is SSA form so that probably makes it easier to
> > validate the control flow. They described this as 'well formed'-ness -
> > the verifier detects if the code is  well-formed and complains if 'the
> > definition of %x does not dominate all of its uses'. My understanding
> > is that the IR you are working with is not SSA-form so this type of
> > validation may not be possible...
> 
> Yes: the IR exposed by the libgccjit API is not SSA-form.  The optimizer
> does use SSA-form internally.
> 
> I think my opinion at the time was that forcing users to create phi
> nodes was unnecessary work for them; let the API do it automatically,
> internally.   I don't know if the loss of this kind of validation is a
> show-stopper; it feels to me more like a fussy API that the user has to
> do extra work to appease.  But I could be wrong.
> 
> > In any case a warning about unreachable bocks may be more appropriate
> > than errors.
> 
> FWIW I've experimented in the past with turning on warnings about
> uninitialized vars, so maybe we need an API setting for validations,
> with each validation having a tri-state:
>   * perform validation, as error
>   * perform validate, as warnings to stderr
>   * don't validate
> 
> (thinking aloud here)

I've filed a bug about the lack of a way to turn off the unreachable
block checking, as:
  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66546