While improving the DMD front-end's constant folding:
    https://github.com/D-Programming-Language/dmd/pull/5229
I found out about DMD issue 14835:
    https://issues.dlang.org/show_bug.cgi?id=14835

Briefly:
///////////////////////////////
module main;

import std.stdio;

void reachIf(bool x)()
{
    if(!x)
        return;
    writeln("reached"); // Warning: statement is not reachable
}

void main(string[] args) {
    reachIf!true();  // prints "reached"
    reachIf!false(); // triggers warning
}
///////////////////////////////

This is, I think, a big problem.

Affected code is rare today, but that is only because DMD's constant folding and value-range-propagation is weak. The more improvements are made in this area, the more common erroneous "statement is not reachable" warnings will become.

Unfortunately, from what I can tell, this bug is just a natural consequence of DMD's current design; I think an ideal fix will not be simple.

Some possible solutions:

1. Defer "not reachable" warnings until compilation has been completed, and only issue the warning if *all* instantiations of the statement were unreachable.

2. For semantic analysis purposes, first instantiate each template using dummy parameters with the widest possible VRP ranges. Only statements found to be "not reachable" in this dummy run should actually generate warnings.

3. ??? I don't know the compiler internals very well, so I may be missing a more elegant solution.

From #1 and #2, #2 is the "correct" choice - if implemented properly, it would produce precisely the results I expect, as a user.

However, I think it would take a huge patch touching many different files and functions to implement. This seems excessive, assuming the only benefit is eliminating some spurious warnings.

#1 would still allow some false positives, but they should be quite rare, and also solvable by the user. Otherwise, this seems like a good approach:

* The size and complexity of the patch should be more reasonable.

* If all messages are deferred, it should be easy to condense the floods of duplicate messages generated by templates. Instead of getting the same message duplicated once per instantiation, you could just have one copy with a `x37` next to it or something.

* Likewise, if desired, messages could be sorted by file and line.

The main disadvantage that I see to approach #1 is that messages will not be printed until compilation is completed - which might be never, if the compiler hangs or something.

Thoughts?

On 10/24/15 1:25 PM, tsbockman wrote:
> While improving the DMD front-end's constant folding:
>      https://github.com/D-Programming-Language/dmd/pull/5229
> I found out about DMD issue 14835:
>      https://issues.dlang.org/show_bug.cgi?id=14835
>
> Briefly:
> ///////////////////////////////
> module main;
>
> import std.stdio;
>
> void reachIf(bool x)()
> {
>      if(!x)
>          return;
>      writeln("reached"); // Warning: statement is not reachable
> }
>
> void main(string[] args) {
>      reachIf!true();  // prints "reached"
>      reachIf!false(); // triggers warning
> }
> ///////////////////////////////
>
> This is, I think, a big problem.

I agree

> Affected code is rare today, but that is only because DMD's constant
> folding and value-range-propagation is weak. The more improvements are
> made in this area, the more common erroneous "statement is not
> reachable" warnings will become.
>
> Unfortunately, from what I can tell, this bug is just a natural
> consequence of DMD's current design; I think an ideal fix will not be
> simple.
>
> Some possible solutions:
>
> 1. Defer "not reachable" warnings until compilation has been completed,
> and only issue the warning if *all* instantiations of the statement were
> unreachable.

This isn't good either. One instantiation of reachIf being able to compile shouldn't be dependent on whether another one was ever used.

> 2. For semantic analysis purposes, first instantiate each template using
> dummy parameters with the widest possible VRP ranges. Only statements
> found to be "not reachable" in this dummy run should actually generate
> warnings.

How does the compiler figure this out? This seems like the halting problem to me.

> 3. ??? I don't know the compiler internals very well, so I may be
> missing a more elegant solution.

I think the easiest solution would be to just give up on worrying about unreachable code if the branch is dependent on a compile time variable that could legitimately change from instantiation to instantiation. In other words, for that instantiation, you obviously don't need to include the code, but you can't declare that the line of code is unreachable.

This means that this will compile:

void foo(int x)()
{
   if(x == 5)
       return;
   writeln("boo!");
}

void main()
{
   foo!5();
}

But this will not:

void main()
{
   enum x = 5;
   if(x == 5)
      return;
   writeln("boo!");
}

Even though they are effectively equivalent. But that's not a good reason to create errors which are obviously untrue. In the second case, the compiler can know definitively that the statement really will never be executed or compiled. In the first case, it can only be sure for that *instance*.

Even this could compile IMO (but a sufficiently smarter compiler may complain):

void foo(int x)() if(x == 5)
{
   if(x == 5)
      return;
   writeln("boo!");
}

Let's not forget that "unreachable statement" errors are really not errors in the sense that it will cause a crash, or corrupt memory. It just means some statements you wrote were wasted effort. It's OK to

-Steve

On Monday, 26 October 2015 at 12:31:37 UTC, Steven Schveighoffer wrote:
>> Some possible solutions:
>>
>> 1. Defer "not reachable" warnings until compilation has been completed,
>> and only issue the warning if *all* instantiations of the statement were
>> unreachable.
>
> This isn't good either. One instantiation of reachIf being able to compile shouldn't be dependent on whether another one was ever used.

I agree this is not ideal, however it would be much better than what we have currently, and the compiler implementation should be relatively simple.

>> 2. For semantic analysis purposes, first instantiate each template using
>> dummy parameters with the widest possible VRP ranges. Only statements
>> found to be "not reachable" in this dummy run should actually generate
>> warnings.
>
> How does the compiler figure this out? This seems like the halting problem to me.

My solution #2 is the same as the one you proposed - the dummy parameter stuff is my vague proposal for a way to actual implement this behavior in the compiler.

The halting problem is no more of an issue than it is for the compiler today. (That is to say, the halting problem leads to false negatives, but not false positives.)

I think the compiler currently does something like this:

void main(string[] args) {
    reachIf!true();  // prints "reached"
    reachIf!false(); // triggers warning
}

// A template will be instantiated and undergo semantic analysis
// once for each combination of CT parameters fed to it in the program.

// reachIf!true pass:
void reachIf(bool x)() // VRP narrows x to true
{
    if(!x) // VRP + constant folding says (!true) always == false
        return; // never reached (this doesn't always generate a warning)
    writeln("reached"); // always reached
}

// reachIf!false pass:
void reachIf(bool x)() // VRP narrows x to false
{
    if(!x) // VRP + constant folding says (!false) always == true
        return; // always reached
    writeln("reached"); // Warning: statement is not reachable
}

My solution #2 would add this before the reachIf!true pass:

// first instantiate the template with the widest possible
// VRP ranges for the CT paramters
void reachIf(bool x)() // VRP says x could be true or false
{
    if(!x) // not constant; cannot be folded
        return; // reachable
    writeln("reached"); // reachable
}

"statement not reachable" warnings would only be generated during this preliminary pass; they would be suppressed in the reachIf!true and reachIf!false passes.

The reason solution #2 could end up being a ton of work, is that a dummy type will have to be created to apply this solution to cases like:

module main;

import std.stdio;

void reachIf(T...)()
{
    if(T.length != 1 || T[0].sizeof != 4)
        return;
    writeln("reached"); // Warning: statement is not reachable
}

void main(string[] args) {
    reachIf!int();  // prints "reached"
    reachIf!long(); // triggers warning

    stdin.readln();
}

(Note that this case can only be reproduced with my constant folding upgrade patch applied.)

In order to apply solution #2 to this code, we need a dummy AliasSeq of indeterminate length, whose elements have a sizeof property of indeterminate value. I strongly suspect that a fake type like that will require explicit support to be added all over the DMD code base; it would be a huge change just to eliminate some spurious warnings.

On 25/10/2015 4:25 AM, tsbockman wrote:
> ///////////////////////////////
> module main;
>
> import std.stdio;
>
> void reachIf(bool x)()
> {
>      if(!x)
>          return;
>      writeln("reached"); // Warning: statement is not reachable
> }
>
> void main(string[] args) {
>      reachIf!true();  // prints "reached"
>      reachIf!false(); // triggers warning
> }
> ///////////////////////////////
>


>
> Thoughts?

Easy to fix:

void reachIf(bool x)()
{
     static if(!x)
         return;
     else
         writeln("reached");
}

The warning is correct, and incredibly annoying.

On Tuesday, 27 October 2015 at 07:50:37 UTC, Daniel Murphy wrote:
> Easy to fix:
>
> void reachIf(bool x)()
> {
>      static if(!x)
>          return;
>      else
>          writeln("reached");
> }
>
> The warning is correct, and incredibly annoying.

Yes, it is easy to work around the problem in my simple example code. Real world examples are not generally so simple, though - often, an equivalent fix would require a `static foreach(...) { ... } else` construct to avoid adding a redundant (and possibly quite complex) predicate.

No, the warning is not correct.

When a "statement is not reachable" warning is generated during analysis of a regular function, it means that that statement can *never* execute, no matter what parameters are fed in.

This is a very useful warning, because why would the programmer deliberately write dead code? Clearly something is wrong (whether in the code being compiled, or the compiler itself).

On the other hand, when a "statement is not reachable" warning is generated based on a specific combination of compile-time parameters, there is likely nothing wrong with the code.

The purpose of templates is code reuse. Forcing the programmer to manually prune each possible instantiation by sprinkling `static if`s with redundant predicates everywhere hinders this goal.

On 10/26/15 1:08 PM, tsbockman wrote:
> On Monday, 26 October 2015 at 12:31:37 UTC, Steven Schveighoffer wrote:
>>> Some possible solutions:
>>>
>>> 1. Defer "not reachable" warnings until compilation has been completed,
>>> and only issue the warning if *all* instantiations of the statement were
>>> unreachable.
>>
>> This isn't good either. One instantiation of reachIf being able to
>> compile shouldn't be dependent on whether another one was ever used.
>
> I agree this is not ideal, however it would be much better than what we
> have currently, and the compiler implementation should be relatively
> simple.
>
>>> 2. For semantic analysis purposes, first instantiate each template using
>>> dummy parameters with the widest possible VRP ranges. Only statements
>>> found to be "not reachable" in this dummy run should actually generate
>>> warnings.
>>
>> How does the compiler figure this out? This seems like the halting
>> problem to me.
>
> My solution #2 is the same as the one you proposed - the dummy parameter
> stuff is my vague proposal for a way to actual implement this behavior
> in the compiler.
>
> The halting problem is no more of an issue than it is for the compiler
> today. (That is to say, the halting problem leads to false negatives,
> but not false positives.)

OK, as long as the default behavior isn't to reject the code, I suppose this is simply an optimization. But the problem I see is that only static ifs that reduce to static if(true) would be considered to cause a short-circuit (e.g. someint <= int.max). Unless the compiler can VRP according to the template constraint, which may be possible in simple circumstances, but not in all circumstances.

It just seems like it's an unnecessary layer. I think we should start with the simple accept all code that branches based on compile-time variables.

> The reason solution #2 could end up being a ton of work, is that a dummy
> type will have to be created to apply this solution to cases like:
>
> module main;
>
> import std.stdio;
>
> void reachIf(T...)()
> {
>      if(T.length != 1 || T[0].sizeof != 4)
>          return;
>      writeln("reached"); // Warning: statement is not reachable
> }

Inherent properties of types that can be variable could be considered variables just like any other size_t or int. Therefore, branching based on that would fall under the same issue.

I think the "ton of work" is avoidable.

-Steve

On 10/27/15 3:50 AM, Daniel Murphy wrote:
> On 25/10/2015 4:25 AM, tsbockman wrote:
>> ///////////////////////////////
>> module main;
>>
>> import std.stdio;
>>
>> void reachIf(bool x)()
>> {
>>      if(!x)
>>          return;
>>      writeln("reached"); // Warning: statement is not reachable
>> }
>>
>> void main(string[] args) {
>>      reachIf!true();  // prints "reached"
>>      reachIf!false(); // triggers warning
>> }
>> ///////////////////////////////
>>
>
>
>>
>> Thoughts?
>
> Easy to fix:
>
> void reachIf(bool x)()
> {
>       static if(!x)
>           return;
>       else
>           writeln("reached");
> }
>
> The warning is correct, and incredibly annoying.
>

Easy to fix, but the warning is incorrect, the statement is reachable if you use reachIf!true.

A statement is not a compiled piece of code.

-Steve

On 10/27/2015 01:35 PM, Steven Schveighoffer wrote:
>>
>> Easy to fix:
>>
>> void reachIf(bool x)()
>> {
>>       static if(!x)
>>           return;
>>       else
>>           writeln("reached");
>> }
>>
>> The warning is correct, and incredibly annoying.
>>
>
> Easy to fix, but the warning is incorrect, the statement is reachable if
> you use reachIf!true.
>
> A statement is not a compiled piece of code.
>
> -Steve

Versions of the same statement in different instantiations are independent. Templates are just a restricted form of hygienic macros.

On Tuesday, 27 October 2015 at 12:28:38 UTC, Steven Schveighoffer wrote:
> On 10/26/15 1:08 PM, tsbockman wrote:
>> My solution #2 is the same as the one you proposed - the dummy parameter
>> stuff is my vague proposal for a way to actual implement this behavior
>> in the compiler.
>>
>> The halting problem is no more of an issue than it is for the compiler
>> today. (That is to say, the halting problem leads to false negatives,
>> but not false positives.)
>
> OK, as long as the default behavior isn't to reject the code, I suppose this is simply an optimization.

Right.

> But the problem I see is that only static ifs that reduce to static if(true) would be considered to cause a short-circuit (e.g. someint <= int.max). Unless the compiler can VRP according to the template constraint, which may be possible in simple circumstances, but not in all circumstances.

I think the next piece of Lionello Lunesu's PR which I am updating might actually do that; I'll have to check later. Regardless, you are correct solution #1 will substantially reduce the opportunities for constant folding.

> It just seems like it's an unnecessary layer. I think we should start with the simple accept all code that branches based on compile-time variables.

Can outline which specific code in the compiler you would modify to accomplish this?

Because at the moment, having looked at the relevant front end code, I don't see a way that is meaningfully simpler than my dummy parameter idea.

>> The reason solution #2 could end up being a ton of work, is that a dummy
>> type will have to be created to apply this solution to cases like:
>>
>> module main;
>>
>> import std.stdio;
>>
>> void reachIf(T...)()
>> {
>>      if(T.length != 1 || T[0].sizeof != 4)
>>          return;
>>      writeln("reached"); // Warning: statement is not reachable
>> }
>
> Inherent properties of types that can be variable could be considered variables just like any other size_t or int. Therefore, branching based on that would fall under the same issue.
>
> I think the "ton of work" is avoidable.

I have only a fuzzy understanding of the compiler's code right now, but it seems to me that the way it is currently structured does not readily allow for simultaneously making information available to `static if` and CTFE, while also hiding it from dead code detection.

I get what you want, but if it's simple to actually make the compiler do it, I don't see how yet. If you do, please give me the names of some files or functions to study in the front end.

On Tuesday, 27 October 2015 at 13:23:51 UTC, Timon Gehr wrote:
> On 10/27/2015 01:35 PM, Steven Schveighoffer wrote:
>>>
>>> Easy to fix:
>>>
>>> void reachIf(bool x)()
>>> {
>>>       static if(!x)
>>>           return;
>>>       else
>>>           writeln("reached");
>>> }
>>>
>>> The warning is correct, and incredibly annoying.
>>>
>>
>> Easy to fix, but the warning is incorrect, the statement is reachable if
>> you use reachIf!true.
>>
>> A statement is not a compiled piece of code.
>>
>> -Steve
>
> Versions of the same statement in different instantiations are independent. Templates are just a restricted form of hygienic macros.

That's how the current implementation works, but that doesn't mean the warning is actually *helpful*.