[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Public WebGL] Infinite loops allowed in WebGL 1.0 currently?



I do not think that the attempt to infer the termination of a loop in GLSL will be very useful. It's not useful because if you'd allow genuinely dynamic loops, then you can't determine when it halts (due to the halting problem). And if you don't allow genuinely dynamic loops, then the behavior is cumbersome (for instance how'd you deal with having a convolution shader you don't need to recompile for every size of kernel you'd like to use).

The unrolling problem in particular is a worrysome spot for the usecase where the length of the loop depends on the input data. It is usually reasonably fast to compile a shader (well, a couple hundred milliseconds is still godawfully slow, but you get my drift). However, once you get to unrolling large loops, like an x/y 128x128 or something, that takes a considerable amount of time, which renders it a useless behavior even for static loops.

A number of my demos have run into the issue of wanting to perform some expensive (but one-time) calculation (like preconvolving an environment map) only to get hung up on unrolling issues. What makes the matter worse, is that for this particular kind of algorithm, you could use an accumulator and a floating point texture, ah but if only that would work everywhere (ah-haw-haw).

I don't think we'll get around to have a way to query if a WebGL implementation supports dynamic loops (and maximum runtimes on them). As an extension perhaps? WEBGL_dynamic_loop?

On Mon, Mar 9, 2015 at 9:01 PM, Ben Constable <bencon@microsoft.com> wrote:
The problem with not unrolling is that not all hardware is able to do this. D3D10 era hardware can have loops encoded in the ISA but I believe that there are D3D9 era parts that cannot do this and a lot of current mobile hardware has inherited this limitation. We don't unconditionally unroll things right now, but sometimes the HLSL compiler decides it wants to unroll things even though I did not tell it to, and then it runs into the same problems that I have.

At the end of the day, we have a good quantity of hardware out there that cannot do dynamic loops at all. The fact that a rich language like GLSL allows you to encode dynamic loops in so many creative ways just means we need to have a tighter specification for controlling against them.

It is conceivable that we can have different behavior depending on the hardware class. The only reason I hesitate a little around that is that the testing matrix for both myself and my customers becomes more complicated every time I do that :) Now, this problem already exists to some extent (somebody writing a big shader and it won't run on mobile) but limiting the damage of this problem for folks building stuff on the web should always be a goal.

When I see validation for loops like the example here I see the halting problem in not very good disguise :) The input to the program can very easily make it impossible to determine if a loop terminates. For example, somebody could preprocess the geometry and textures to ensure that their shader always terminates their while(true) loops, but there is no way for a compiler to distinguish this. I see our static analysis software we use internally struggle with stuff like this all of the time and people end up using pragmas or more complicated histrionics to solve the issue.

Right now I see some options:

a) We can go ahead and reject code like the below on certain classes of hardware with a compile error, and permit it on most hardware with some combination of attributes on the loops. I think this is ultimately more friendly developers. Does "platform dependent" not cover the case where we suspect the loop is problematic and reject compilation?
b) We can harden the specification somewhat for loops to avoid allowing them to resemble while(true). With shader code this actually adds value because it forces closer examination of what is actually desired. I don't have huge high hopes for this given that we have stuff in the wild relying on it, but I can always have some hope :)

On another fork I saw Jamie mention a desire to do some kind of an amend here.

-----Original Message-----
From: Kenneth Russell [mailto:kbr@google.com]
Sent: Friday, March 6, 2015 5:14 PM
To: Ben Constable
Cc: public webgl
Subject: Re: [Public WebGL] Infinite loops allowed in WebGL 1.0 currently?

On Fri, Mar 6, 2015 at 1:04 PM, Ben Constable <bencon@microsoft.com> wrote:
> We were looking at a bug in IE recently and came across an interesting case:
>
> http://threejs.org/examples/#webgl_materials_parallaxmap
>
> This has this fragment of GLSL code:
>
>                                "for ( int i = 0; i == 0; i += 0 ) {",
>
> This is obviously an infinite loop. I am assuming that the site is
> working because the code is never hit in practice.
>
> The way that we translate GLSL, this is a bit tricky for us. It
> appears that ANGLE is outputting [loop] in HLSL, and on most hardware
> this will happily generate an infinite loop that causes TDRs in the
> shader (we can make Chrome TDR using loop constructs like this).
>
> The specification for loops in GLSL seems to have a lot of effort put
> into preventing unverifiable loops – is the case of a zero increment
> an oversight in the specification? I would love to return an error for
> this kind of case but if I do that now, I will end up not working on a
> site that works in ANGLE based browsers, and this is not good for interoperability.

It looks like the shader more precisely does

  for ( int i = 0; i == 0; i += 0 ) {
    if ( heightFromTexture <= currentLayerHeight ) {
      break;
    }
    currentLayerHeight += layerHeight;
    // ...
  }

GLSL ES 1.0.17 appendix A allows for_headers including the form:

  loop_index += constant_expression

and section 6.3 "Iteration" says

  Non-terminating loops are allowed. The consequences of very long or non-terminating loops are platform dependent.

so strictly speaking, the shader should validate.

There are surely many shaders using conditional breaks to work around the lack of dynamic upper bounds in loop conditions. I'm pretty sure I've seen similar shaders using constructs like

  while (true) {
    if (something)
      break;
    // ...
  }

It would be ideal if we could figure out a solution allowing your GLSL translator to run these shaders. If the issue is that you unconditionally unroll loops, can you avoid doing so only in these problematic situations?

-Ken