Self-referential instruction from jump threading

Hello,

After investigating PR14133, I've discovered that jump threading can output self-referential instructions:
%inc.us = add nsw i32 %inc.us, 1

At least in the test case for that bug report, the relevant code is later deleted (perhaps it is unreachable), and so this does not cause a problem. Unfortunately, when vectorization is enabled, this instruction causes BBVectorize to hang. Should I make BBVectorize ignore this kind of thing, on the assumption that it occurs only in unreachable (or otherwise dead) code, or should this be fixed at the source (in jump threading in this case)?

Thanks again,
Hal

Hal Finkel wrote:

Hello,

After investigating PR14133, I've discovered that jump threading can output self-referential instructions:
%inc.us = add nsw i32 %inc.us, 1

At least in the test case for that bug report, the relevant code is later deleted (perhaps it is unreachable), and so this does not cause a problem. Unfortunately, when vectorization is enabled, this instruction causes BBVectorize to hang. Should I make BBVectorize ignore this kind of thing, on the assumption that it occurs only in unreachable (or otherwise dead) code, or should this be fixed at the source (in jump threading in this case)?

The way to check whether it's valid is with the verifier. If jump threading were emitting that in a reachable block it would fail the verifier, in an unreachable block it would pass the verifier. Your pass gets to assume its input passes the verifier, and must produce output that does as well. That leads to the conclusion that if you see one of these in your input, then its parent block must be unreachable.

Nick

Hi Hal,

After investigating PR14133, I've discovered that jump threading can output self-referential instructions:
%inc.us = add nsw i32 %inc.us, 1

such instructions are valid in unreachable basic blocks.

At least in the test case for that bug report, the relevant code is later deleted (perhaps it is unreachable), and so this does not cause a problem. Unfortunately, when vectorization is enabled, this instruction causes BBVectorize to hang. Should I make BBVectorize ignore this kind of thing, on the assumption that it occurs only in unreachable (or otherwise dead) code, or should this be fixed at the source (in jump threading in this case)?

All such instructions are dead, as they always live in unreachable basic blocks,
so there is no point in trying to optimize them.

Ciao, Duncan.

From: "Duncan Sands" <baldrick@free.fr>
To: llvmdev@cs.uiuc.edu
Sent: Monday, October 22, 2012 4:40:50 AM
Subject: Re: [LLVMdev] Self-referential instruction from jump threading

Hi Hal,

> After investigating PR14133, I've discovered that jump threading
> can output self-referential instructions:
> %inc.us = add nsw i32 %inc.us, 1

such instructions are valid in unreachable basic blocks.

Okay, thanks!

> At least in the test case for that bug report, the relevant code is
> later deleted (perhaps it is unreachable), and so this does not
> cause a problem. Unfortunately, when vectorization is enabled,
> this instruction causes BBVectorize to hang. Should I make
> BBVectorize ignore this kind of thing, on the assumption that it
> occurs only in unreachable (or otherwise dead) code, or should
> this be fixed at the source (in jump threading in this case)?

All such instructions are dead, as they always live in unreachable
basic blocks,
so there is no point in trying to optimize them.

Fair enough. I'll change BBVectorize to ignore blocks for which isReachableFromEntry is false.

-Hal

From: "Nick Lewycky" <nicholas@mxc.ca>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Monday, October 22, 2012 4:25:36 AM
Subject: Re: [LLVMdev] Self-referential instruction from jump threading

Hal Finkel wrote:
> Hello,
>
> After investigating PR14133, I've discovered that jump threading
> can output self-referential instructions:
> %inc.us = add nsw i32 %inc.us, 1
>
> At least in the test case for that bug report, the relevant code is
> later deleted (perhaps it is unreachable), and so this does not
> cause a problem. Unfortunately, when vectorization is enabled,
> this instruction causes BBVectorize to hang. Should I make
> BBVectorize ignore this kind of thing, on the assumption that it
> occurs only in unreachable (or otherwise dead) code, or should
> this be fixed at the source (in jump threading in this case)?

The way to check whether it's valid is with the verifier. If jump
threading were emitting that in a reachable block it would fail the
verifier, in an unreachable block it would pass the verifier. Your
pass
gets to assume its input passes the verifier, and must produce output
that does as well. That leads to the conclusion that if you see one
of
these in your input, then its parent block must be unreachable.

Makes sense, thanks!

-Hal