llvm dev - Dec 2011 - [LLVMdev] The nsw story

On Dec 5, 2011, at 7:42 PM, Dan Gohman wrote:
> For example, suppose we want to convert the && to &, and the ?:
to a
> select, in this code:
> 
> if (a && (b ? (c + d) : e)) {
> 
> because we have a CPU architecture with poor branch prediction, or
> because we want more ILP, or because of some other reason. Here's what
the
> LLVM IR for that might look like:
> 
>   %t0 = add nsw i32 %c, %d
>   %t1 = select i1 %b, i32 %t0, i32 %e
>   %t2 = icmp ne i32 %t1, 0
>   %t3 = and i1 %a, %t2
>   br i1 %t3, ...
> 
> The extra branching is gone, yay. But now we've put an add nsw out
there
> to be executed unconditionally. If we make the select an observation
> point, we'd have introduced undefined behavior on a path that
didn't
> previously have it.
> 
> A foodtaster instruction doesn't really solve this problem, because
> we'd have to put it between the add and the select, and it would be
> just as problematic.
> 
> The current definition of nsw is an attempt to avoid arbitrary
> limitations and keep the system as flexible as possible.
> 
> One could argue that aggressive speculation is a low-level optimization
> better suited to CodeGen than the optimizer, as LLVM divides them, and
> that perhaps the cost for providing this level of flexibility in the
> optimizer is too high, but that's a different argument.
The optimizations we're talking about are forms of safe
speculation. Doing that at IR level is fine.

Hardware support for NaT bits + check instructions have been popping
up on this message thread. Hardware speculation exists solely to
support unsafe speculation, in which certain operations need to be
reexecuted under certain conditions. It is not something we would ever
want to represent in IR. It isn't ammenable to CFG+SSA form.

Runtime checking for undefined behavior would be implemented as
overflow checks, etc. by the front end. I don't think it's related to
unsafe speculation. In other words, I don't see the purpose of a
"check/foodtaster" instruction.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111206/44f22850/attachment.html>

Andrew Trick <atrick at apple.com> writes:
> The optimizations we're talking about are forms of safe
> speculation. Doing that at IR level is fine.
>
> Hardware support for NaT bits + check instructions have been popping
> up on this message thread. Hardware speculation exists solely to
> support unsafe speculation, in which certain operations need to be
> reexecuted under certain conditions. It is not something we would ever
> want to represent in IR. It isn't ammenable to CFG+SSA form.
>
> Runtime checking for undefined behavior would be implemented as
> overflow checks, etc. by the front end. I don't think it's related
to
> unsafe speculation. In other words, I don't see the purpose of a
> "check/foodtaster" instruction.
The purpose of all of these discussions is to alleviate the
computational explosion of static analysis that Dan described in the
presence of nsw bits.  The point is to reduce the search space for
static checking.  If we don't care about that, then all of this
discussion is moot.  :)

                                  -Dave

On Dec 6, 2011, at 2:31 PM, David A. Greene wrote:
> Andrew Trick <atrick at apple.com> writes:
> 
>> The optimizations we're talking about are forms of safe
>> speculation. Doing that at IR level is fine.
>> 
>> Hardware support for NaT bits + check instructions have been popping
>> up on this message thread. Hardware speculation exists solely to
>> support unsafe speculation, in which certain operations need to be
>> reexecuted under certain conditions. It is not something we would ever
>> want to represent in IR. It isn't ammenable to CFG+SSA form.
>> 
>> Runtime checking for undefined behavior would be implemented as
>> overflow checks, etc. by the front end. I don't think it's
related to
>> unsafe speculation. In other words, I don't see the purpose of a
>> "check/foodtaster" instruction.
> 
> The purpose of all of these discussions is to alleviate the
> computational explosion of static analysis that Dan described in the
> presence of nsw bits.  The point is to reduce the search space for
> static checking.  If we don't care about that, then all of this
> discussion is moot.  :)
> 
>                                  -Dave
Right. I can see how a value-undefined-if-poison marker could yield more precise
static analysis. I didn't mean to discourage that approach, although I'm
not aware of any imminent problem that it solves.

-Andy