Differential D37463
Fix miscompile in LoopSink pass Authored by DaniilSuchkov on Sep 5 2017, 3:38 AM.
Details
It was allowed by llvm::canSinkOrHoistInst to sink non-invariant loads into loops but it is illegal because it can introduce new data races. For example: b = *p; for (int i = 0; i < N; i++) a[i] = b; Assuming a is a thread local value, it should always contain a single value. If it were to contain different values at different indices, that would be a miscompile.
Diff Detail
Event TimelineComment Actions Thanks for raising the issue. But I'm not sure if this the right fix
Additionally, about the original testcase, the data race is there even without loopsink optimization as the load outside of the loop is not guarded by any locks. I'm not a C++ standard expert and am not sure if data race like this is considered as undefined behavior (if yes, then it's legal for compiler to sink the load down to the loop to break the "everything in a[] should be the same" assumption) Put it another way, is it legal to hoist the load for the following load with potential racy condition? for (i = 0; i < N; ++i) a[i] = *p; Comment Actions In C/C++, your example has undefined behavior. From the C++ standard: "The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other. Any such data race results in undefined behavior." Comment Actions From comment to canSinkOrHoistInst: /// If SafetyInfo is null, we are checking for sinking instructions from /// preheader to loop body (no speculation). So I'm just checking if we are going to sink load into loop.
Yes. "No race" is one of possible cases of data race. Comment Actions I need to read what C++ specification says about this particular issue, but basically LLVM is not only used to compile C++. This situation can be illegal in other languages (again, need to dig more through specifications). My proposal is to add an option that prohibits this transform and set it to false by default, with abitily to turn it off for languages where it is prohibited. Comment Actions Actually the answer is here: https://llvm.org/docs/Atomics.html#notatomic
So, this behavior of LoopSink is not a bug. Comment Actions Actually, there might be a bug here in the handling of "unordered" atomic loads... I haven't verified, but we might need to special-case them in LoopSink. Comment Actions LoopSink uses canSinkOrHoistInst from LICM to check whether instruction can be sunk or not. This check rejects all loads with isUnordered() == true (see http://llvm.org/docs/Atomics.html#atomics-and-ir-optimization). It looks like "unordered" atomics are handled in a right way: they are never sunk into loops. Comment Actions LLVM has a memory model. If this violates LLVM's memory model, it's a bug. Comment Actions Strongly agreed with this. Neither the C++ memory model or the Java memory model are directly relevant to this discussion. We should focus on the LLVM memory model exclusively when defining LLVM bugs and revise the LLVM memory model if needed to support one of our frontend languages. Reading through the discussion, it sounds like we have correctly concluded there was no bug here (at least for standard non-atomic loads and stores). Reading through the code, it also looks like ordered atomics are handled conservatively and not sunk. I think there might be some further investigation needed for unordered atomics, but I will take that offline with Daniil before returning to this thread. Comment Actions Returning to this point, the conclusion I would reach reviewing our Atomics documentation is that sinking an unordered atomic into a loop must be disallowed, because doing so duplicates the load which is disallowed. The relevant section of the documentation is: http://llvm.org/docs/Atomics.html#unordered, specifically the Notes for Optimizers section. Here's the full text of the section under discussion: Notes for optimizers In terms of the optimizer, this *prohibits any transformation that transforms a single load into multiple loads*, transforms a store into multiple stores, narrows a store, or stores a value which would not be stored otherwise. Some examples of unsafe optimizations are narrowing an assignment into a bitfield, *rematerializing a load*, and turning loads and stores into a memcpy call. Reordering unordered operations is safe, though, and optimizers should take advantage of that because unordered operations are common in languages that need them. The important bits are in *bold*. The first highlighted clause could be interpreted to be a weaker constraint that it first seems. In particular, it could be read as only disallowing *splitting* a load into multiple pieces, and not disallowing *duplicating* an load. Internally, several folks read it that way. I believe that is an incorrect interpretation and that duplication must also be disallowed by the text. My reasoning is as follows: Sinking a load into the header of a loop with a trip count > 1 increases the number of times the load is run dynamically. Rematerialization (which is explicitly allowed as a disallowed transformation) is the insertion of loads by the register allocator at use sites. LoopSinking and rematerialization end up producing *exactly the same code* on the following example: L = load atomic %p call_which_clobbers_all_regs(); use L } Both transforms would want to produce: while (foo()) { call_which_clobbers_all_regs(); L = load atomic %p use L } If this were legal for LoopSink, then it would also be legal for rematerialization. And it's definitely not, as explicitly stated in the text. As such, it must be the case that LoopSink is disallowed for this case as well, which requires the broader interpretation of the initial sentence. Given this, I must conclude that LoopSink is currently buggy as we do sink unordered atomic loads into loops. |