(If this thread is becoming tiresome, let me know. This newbie is trying to understand some of what's going on; clearly you've thought about it way more than I have, and I can understand if you want to stop thinking about it!) On Mon, Dec 5, 2011 at 2:22 PM, Dan Gohman <gohman at apple.com> wrote:> On Dec 5, 2011, at 11:55 AM, Paul Robinson wrote: > > > > On Thu, Dec 1, 2011 at 9:37 AM, David A. Greene <greened at obbligato.org> > wrote: > > Dan Gohman <gohman at apple.com> writes: > > > > > Prohibiting poison values from propogating through memory would mean > > > that the reg2mem pass would no longer be a semantics-preserving pass. > > > > Or it means you couldn't demote those values. > > > > If reg2mem is constructing spill slots, or address-not-taken locals, I > could > > see classifying those as okay-to-poison. You would not want statics or > globals > > or pointer-addressed memory to be poisonable, as those should be treated > > as being observable locations. > > > > So, it's not really "all of memory" that could be poisoned, only these > > compiler-generated things. > > This would mean that it's not valid to do store-to-load propagation > in the optimizer if the pointee might be a global variable. That > would mean the loss of real optimizations. > > And it would still mean that non-volatile store instructions suddenly > can have side effects beyond just writing to their addressed memory. > That would be surprising. > > I think Dave also suggested making select instructions be > observation points. That would mean that select instructions would > have side effects. Again, that would be surprising. > > Dan > > Back in your first message on this thread, you did say:>The poison would >propagate down the def-use graph until it reaches an instruction that >is capable of triggering the undefined behavior.So, somebody somewhere has to be capable of triggering the undefined behavior. What instructions did you have in mind? If the store, select, and compare instructions aren't appropriate, which ones are? I don't think this next suggestion was on your list, so here goes: Drawing from the Itanium example, we could define a new 'check' instruction, which would explicitly trigger the undefined behavior if its operand is poisoned, or produce a known-safe value otherwise. Yes, the IR would have to be sprinkled with these things; but only outputs of 'nsw' kinds of operations would subsequently need a 'check' to sanitize them. So, if a potentially poison value propagates down the def-use graph until it reaches a store/select/compare, that instruction must be preceded by a 'check' that will sanitize the value. (Or maybe we should call it the 'foodtaster' instruction, which protects the important instructions from poison...) Separating out the induce-undefined-behavior instruction means the existing semantics of store/select/compare are unaffected, the main consequences being that you can't move these guys past the 'check' that feeds them. But that constraint would exist automatically anyway, right? because you couldn't move an instruction up prior to where its input values are defined. Clever/optimal placement of 'check' becomes a topic of interest, but that's kind of the point of the exercise. Pogo -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111205/fc15c0af/attachment.html>
On Dec 5, 2011, at 4:44 PM, Paul Robinson wrote:> (If this thread is becoming tiresome, let me know. This newbie is trying to > understand some of what's going on; clearly you've thought about it way more > than I have, and I can understand if you want to stop thinking about it!) > > On Mon, Dec 5, 2011 at 2:22 PM, Dan Gohman <gohman at apple.com> wrote: > On Dec 5, 2011, at 11:55 AM, Paul Robinson wrote: > > > > On Thu, Dec 1, 2011 at 9:37 AM, David A. Greene <greened at obbligato.org> wrote: > > Dan Gohman <gohman at apple.com> writes: > > > > > Prohibiting poison values from propogating through memory would mean > > > that the reg2mem pass would no longer be a semantics-preserving pass. > > > > Or it means you couldn't demote those values. > > > > If reg2mem is constructing spill slots, or address-not-taken locals, I could > > see classifying those as okay-to-poison. You would not want statics or globals > > or pointer-addressed memory to be poisonable, as those should be treated > > as being observable locations. > > > > So, it's not really "all of memory" that could be poisoned, only these > > compiler-generated things. > > This would mean that it's not valid to do store-to-load propagation > in the optimizer if the pointee might be a global variable. That > would mean the loss of real optimizations. > > And it would still mean that non-volatile store instructions suddenly > can have side effects beyond just writing to their addressed memory. > That would be surprising. > > I think Dave also suggested making select instructions be > observation points. That would mean that select instructions would > have side effects. Again, that would be surprising. > > Dan > > Back in your first message on this thread, you did say: > > >The poison would > >propagate down the def-use graph until it reaches an instruction that > >is capable of triggering the undefined behavior. > > So, somebody somewhere has to be capable of triggering the undefined > behavior. What instructions did you have in mind? If the store, > select, and compare instructions aren't appropriate, which ones are?A call to printf (I/O), a volatile memory operation, etc. These things can never be speculated. They are essentially the anchors of the system.> I don't think this next suggestion was on your list, so here goes: > Drawing from the Itanium example, we could define a new 'check' > instruction, which would explicitly trigger the undefined behavior if its > operand is poisoned, or produce a known-safe value otherwise. Yes, the > IR would have to be sprinkled with these things; but only outputs of 'nsw' > kinds of operations would subsequently need a 'check' to sanitize them. > > So, if a potentially poison value propagates down the def-use graph > until it reaches a store/select/compare, that instruction must be > preceded by a 'check' that will sanitize the value. > > (Or maybe we should call it the 'foodtaster' instruction, which protects > the important instructions from poison...) > > Separating out the induce-undefined-behavior instruction means the > existing semantics of store/select/compare are unaffected, the main > consequences being that you can't move these guys past the 'check' > that feeds them. But that constraint would exist automatically anyway, > right? because you couldn't move an instruction up prior to where its > input values are defined. > > Clever/optimal placement of 'check' becomes a topic of interest, but > that's kind of the point of the exercise.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. Dan
Dan Gohman <gohman at apple.com> writes:> 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.Unless the undefined behavior only triggered if the select actually produced a poisoned result. Then it should have the same behavior as the branch, no?> 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.Or you put it immediately after the select.> 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.No, I think we want the flexibility. But I believe there are sane ways to do this. -Dave
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>