2011/12/14 Rafael Ávila de Espíndola <rafael.espindola at gmail.com>:>> We first perform a speculation transformation, hoisting all of the >> code above the %overflow_check branch: >> >> %t0 = add nsw i32 %a, %b >> %t1 = sext i32 %t0 to i64 >> %t2 = ashr i64 %t1, 31 >> %t3 = add i64 %t2, 1 >> %t5 = icmp ult %t3, 2 >> %t6 = udiv i1 1, %t5 >> br i1 %overflow_check, label %no_overflow, label %end >> >> no_overflow: >> >> Was this valid? >> >> If nsw overflow is immediate undefined behavior, this transformation >> would break the program, because the overflow is no longer guarded >> by %overflow_check. But a premise of this exercise is that we want >> to be able to speculate add nsw instructions. For now, let's assume >> that there's a way to define nsw which permits this, with some kind >> of deferred undefined behavior semantics. > > Could we say that moving the udiv was invalid? It is a instruction > witch can cause undefined behavior and doing the move makes it exposed > to poison values in conditions it was not before.Note that this matches existing practice: IIRC, for a testcase like the given testcase, LICM will hoist everything except the div instruction. -Eli
On Dec 14, 2011, at 12:11 PM, Eli Friedman wrote:> 2011/12/14 Rafael Ávila de Espíndola <rafael.espindola at gmail.com>: >>> We first perform a speculation transformation, hoisting all of the >>> code above the %overflow_check branch: >>> >>> %t0 = add nsw i32 %a, %b >>> %t1 = sext i32 %t0 to i64 >>> %t2 = ashr i64 %t1, 31 >>> %t3 = add i64 %t2, 1 >>> %t5 = icmp ult %t3, 2 >>> %t6 = udiv i1 1, %t5 >>> br i1 %overflow_check, label %no_overflow, label %end >>> >>> no_overflow: >>> >>> Was this valid? >>> >>> If nsw overflow is immediate undefined behavior, this transformation >>> would break the program, because the overflow is no longer guarded >>> by %overflow_check. But a premise of this exercise is that we want >>> to be able to speculate add nsw instructions. For now, let's assume >>> that there's a way to define nsw which permits this, with some kind >>> of deferred undefined behavior semantics. >> >> Could we say that moving the udiv was invalid? It is a instruction >> witch can cause undefined behavior and doing the move makes it exposed >> to poison values in conditions it was not before.We could, but it would preclude desirable optimizations.> Note that this matches existing practice: IIRC, for a testcase like > the given testcase, LICM will hoist everything except the div > instruction.LICM on ToT hoists the div. Even speculatively. The other thing is that div is just one example. The problem could also come up with an array load with an index could be safe to speculate if the index is known to be bounded. isDereferenceablePointer currently doesn't know how to do this, but it'll probably get smarter some day. Dan
Rafael Ávila de Espíndola
2011-Dec-17 14:42 UTC
[LLVMdev] nsw is still logically inconsistent
> LICM on ToT hoists the div. Even speculatively. > > The other thing is that div is just one example. The problem could > also come up with an array load with an index could be safe to > speculate if the index is known to be bounded. isDereferenceablePointer > currently doesn't know how to do this, but it'll probably get > smarter some day.So, looking at just this example, it looks like semantics we assign to poison values have to do one of *) Avoid the udiv being moved, since a valid removal of nsw would create a program that is now exposed to undefined behavior. *) Say that use of poison values only produces other poison values, not undefined behavior. The second option would give us a lot of liberty to move instruction around, but is a major change to what the IL looks like these days. In particular: *) removing a nsw would become invalid, as it would change a poison value to a 0, which would cause udiv to have undefined behavior again. *) Codegen would have to be very careful not to produce undefined behavior when handling instructions that potentially see poison values. If we really want the ability to expose instructions with side effects to poison, maybe the best thing to do is to have poison resistant variants. For example, we would say that moving the udiv is invalid, but it could be replaced with a "udiv poison i1 1, %t5". The poison variant has the same definition as udiv, put produces poison when t5 is 0 (or poison) and therefore can be moved. The same goes for speculating a load.> Dan >Cheers, Rafael