Proposal for SentinelInputRange

[Ary Borenszweig]

On 2/28/13 2:32 PM, Steven Schveighoffer wrote:
> On Thu, 28 Feb 2013 12:13:27 -0500, Dmitry Olshansky
> <dmitry.olsh at gmail.com> wrote:
>
>> No as a compiler will take it (or may depending on its brain) that 0
>> is what you want to test *first*. It may speed things up if branch is
>> almost always taken but its not the case with sentinel. Thus its jsut
>> dead code that needs to be decoded, evalutated and skipped (as
>> predicated) *before* doing switch jump.
>
> Well, according to lexer.c, case 0 is the first case.  Why does that not
> make the compiler decide to test 0 first?
>
> Answer: it actually doesn't care, the switch compiles to a jump table.
> Which still begs the question, why can't the compiler make the leap to
> the equivalent code with a range?
>
> are these not semantically equivalent?
>
> if(x == 0)
> {
>     // case for 0
> }
> else
> {
>     switch(x)
>     {
>        case 1:
>           // case for 1;
>           break;
>        case 2:
>           // case for 2;
>           break;
>        ... // cases for everything but 0
>     }
> }
>
> vs.
>
> switch(x)
> {
>     case 0:
>        // case for 0;
>        break;
>     case 1:
>        // case for 1;
>        break;
>     case 2:
>        // case for 2;
>        break;
>     ... // cases for everything but 0
> }
>
> They seem semantically identical.  It would not be impossible for an
> optimizer to make this leap.
>
> Combined with inlining, the above could be:
>
> if(r.empty)
> {
>     // case for 0;
> }
> else
>    ...
>
> and still be optimized the same.  I'm not saying it happens, I'm saying
> it's possible.  I have read several posts here claiming that llvm does
> this (I haven't tried this myself, but it sounds likely true).

It is true. Compiling this Crystal program:

---
def my_fun(num)
   num == 0
end

num = ARGV[0].to_i

if my_fun(num)
   puts 0
else
   case num
   when 1
     puts 1
   when 2
     puts 2
   end
end
---

I see this somewhere in the generated llvm code:

switch i32 %25, label %crystal_main.exit [
     i32 0, label %then.i
     i32 1, label %then16.i
     i32 2, label %then20.i
   ]