Repository navigation
Weird inconsistency in types on IL evaluation stack #9130
Description
Ecma-335 claims:
It shall be possible, with a single forward-pass through the CIL instruction stream for any method, to infer the exact state of the evaluation stack at every instruction (where by “state” we mean the number and type of each item on the evaluation stack).
Unfortunately the reality of the runtime seems to be completely different.
The following function demonstrates how weird things can get: (full IL program)
.method public static native int Int32OrNative(int32 val)
{
.locals init (bool v)
ldc.i4.0
// Comment out this stloc/ldloc pair to change the behavior:
stloc.0
ldloc.0
brtrue use_native_int
use_i4:
ldarg.0
br after_if
// IL evaluation stack here is [int32] if coming from use_i4,
// or [native int] if coming from use_native_int.
after_if:
ldc.i4.1
add // is this a 32-bit addition or native int addition?
ret
use_native_int:
// unreachable code block pushing 'native int',
// but the runtime only knows it's unreachable if we
// don't have the stloc/ldloc pair above
ldarg.0
conv.u
br after_if
}
Calling Int32OrNative(int.MaxValue) returns 2147483648.
But if you comment out the stloc/ldloc pair at the start of the function, the return value changes to -2147483648.
From what I've found, the addition happens in 64-bit (native int size) if the JIT sees any code path from the start of the function to the add that passes a native int on the stack (even if that's not actually the code path taken at runtime). This is what happens if you have the stloc/ldloc pair in there. [note that the type information is propagated through a backwards branch, contrary to Ecma-335]
On the other hand, without the stloc/ldloc pair, some form of constant folding seems to happen, marking the use_native_int block unreachable in an earlier phase of the JIT, and thus the addition happens in 32-bit.
I don't suppose there's any documentation on this behavior? It seems highly unexpected that implementation details of the runtime (when constant folding happens) can affect the visible behavior.
(the reason I'm asking: I'm trying to figure out how to correctly decompile such code in icsharpcode/ILSpy#901)
Activity
mikedn commentedon Oct 13, 2017
Eh, the dangers of optimizing while importing IL. The importer figures out that the conditional branch is useless and removes it. Now the basic block that loads a native int on the evaluation stack is never imported so the addition is never converted to a native int addition.
AndyAyersMS commentedon Oct 13, 2017
We can probably add in some fairly cheap defensive checks to catch cases like this, without abandoning the TP and CQ benefits from importer branch folding.
For instance when import folding a branch, if the target native int is not 32 bits and the stack at the branch contains a 32 bit integer, the jit should go ahead and import the other path even though the code there is unreachable.
The jit will eventually toss the unreachable code, but will now see its impact on the types in the reachable code.
We could broaden this to check for the other reimport triggers: float/double and 0/byref, though I am not sure the differences the other cases are observable when those paths are unreachable. Maybe float/double?
mikedn commentedon Oct 13, 2017
Yeah, this issue has a similar impact on floating point operations when SSE2 is used (always in the case of RyuJIT). You end up with either
addssoraddsdso it's possible to get different results for certain fp operations and numbers.It's interesting how this never affected JIT32 - native int was 32 bit and its use of x87 probably also means that fp operations aren't affected as well.
Too bad we can't somehow simulate the import, after all we don't need the IR, just the stack state. But the stack contains IR nodes so...
AndyAyersMS commentedon Oct 16, 2017
Thinking about this some more, we can't detect this problem at the point we fold the branch.
Consider an ABCD diamond where A's branch is foldable and A is stack emtpy at the branch. If B pushes
int32and C pushesnative intthen type on the stack at entry to D will depend on whether the jit folded the branch in A.Detection has to occur via an examination of the incoming evaluation stack at D (or generally, examination of the incoming evaluation stack for any block that is a successor in a spill clique).
The questions now are:
Right now I am thinking of waiting until a post pass. When importing the jit tracks two things: the set of spill cliques that were created, and whether or not any branches got folded.
A method is then vulnerable to mistyping if
If the method is vulnerable to mistyping, then possible recovery options include
Current thinking is to keep track track the skipped blocks; we could do this fairly cheaply with some new block flag. So then in a post process, if the method is vulnerable, the jit would rewalk all blocks, and if any was marked as skipped and has not yet been imported, schedule it for importation.
AndyAyersMS commentedon Oct 17, 2017
Have started in on fixing this -- one complication that comes up is that the "before" stack state contribution for a given predecessor only exists at the end of importing the predecessor . So when folding, we need to act like we're going to import both successors and capture this state in a pending block descriptor, but defer actual importation of the block that is unreachable.
AndyAyersMS commentedon Oct 17, 2017
Still searching for an approach that fits in well with the existing code. There are a number of crosscutting concerns (in particular verifier mode) that are not easy to test properly in CoreCLR.
I have one line of attack that creates a second import block list, for "deferred" import blocks -- the blocks that are former targets of the now-folded conditional branches. The deferral lets the jit capture the before state. But adding this state increases the combinatorics in
impImportBlockPendingconsiderably, as blocks can move from deferred to pending, etc. Also there's a second level of iterative closure process around the current iterative closure, when considering deferred blocks the importer may do more folding and create a new set of deferred blocks. If I go this route I probably want to do some preliminary refactoring to make the current importer block state a bit more explicit first and try and verify that that initial rework doesn't alter behavior any.The detection code only sees a handful of examples where mis-importation is possible in mscorlib (23 methods out of 25000 or so, and of those 23, 17 are various instantiations of
System.Collections.Generic.GenericArraySortHelper<T>:SwapIfGreaterWithItems. So I'm also considering something low tech like disabling folding when the potential for mis-importation is detected, and then just re-importing everything. Not sure yet if this can be done surgically.AndyAyersMS commentedon Oct 18, 2017
Overall, there are 743 instances where the problem detector fires in the 142915 methods in the jit-diffs fx set, so when jitting, about one method in 200 would trigger the recovery process.
AndyAyersMS commentedon Oct 18, 2017
I have a prospective fix for this: master...AndyAyersMS:ReimportAllWhenFoldingIsRisky. Have not tested it extensively so it may still need work.
It causes some diffs in jit-diffs:
(and as noted above reimportation is triggered 743 times total, sometimes more than once in a root method because of repeated inlining of a problematic method). I haven't looked through all the diffs in detail but many of them seem to be artifacts of not fully resetting the method state when re-importing -- eg some otherwise unused stack slots get zeroed.
JIT32 has the same logic for branch folding in the importer and has likely had it for a while. I am going to look back at older desktop version and see where the problem first surfaced.
AndyAyersMS commentedon Oct 19, 2017
Hmm, for JIT32 we probably can't see these issues since native int/int32 have the same representation, and the use of x87 masks the float/double case. So instead I'll look at the legacy JIT64's behavior.
AndyAyersMS commentedon Oct 19, 2017
JIT64 seems to always produce -2147483648.
AndyAyersMS commentedon Oct 19, 2017
Looking at ECMA-335 it appears that the order in which branch targets are considered during type merging is unspecified. And since int32 is verifier-assignable to native int and vice versa (via I.8.7.3 (4)), it looks like conforming implementations can arrive at different answers for the type of the element on the stack in cases like the ABCD diamond or the example code above.
The text of III.1.7.5 does not seem to rule out the case that multiple "correct" typings are possible, just that "a single forward pass" can reliably find one of the (possibly many) correct typings, if there is one.
The backwards rule only applies to points in the code that can only be reached from program entry via a path that ends with a backwards branch, though one might plausibly extend it to say that in general, backwards branches should not provide any new type information to blocks that can also be reached via paths that end in forwards branches, though doing so would still not remove the potential for multiple correct typings.
So I am tempted to say that the example above does not have a single well defined typing, and the current RyuJit behavior, while undesirable, is not technically wrong. We may still want to fix this but this part of the jit is delicate and these cases are rare so we best tread carefully.
@CarolEidt any thoughts here? Am I missing something?
CarolEidt commentedon Oct 24, 2017
@AndyAyersMS sorry for the delay. I don't think you're missing anything. It has previously been pointed out that the order in which the branches are considered is unspecified (and this can also impact the type of class objects sitting on the stack, not just integers). When this issue has come up before, the conclusion has been that there is no good way to tighten this up without changing existing behavior.
AndyAyersMS commentedon Oct 25, 2017
@dgrunwald, given ambiguities in the spec, the low frequency of these cases, the risk of a changes, and fact that RyuJit diverged from Jit64 in this area without causing any noticeable problems, we are unlikely to change the RyuJit's behavior.
dgrunwald commentedon Oct 28, 2017
Well, I'm looking for an explanation of how to infer IL stack types in ILSpy. I just came up with this IL code while looking for edge cases in the runtime's behavior.
It's not clear whether the single-pass logic in the spec is good enough for real-world IL code. C++/CLI-generated IL seems potentially problematic; and then of course there's obfuscators that like to re-order blocks and stuff invalid opcodes into unreachable blocks.
I think I'm going to implement something like this for ILSpy:
AndyAyersMS commentedon Jan 18, 2018
@dgrunwald your algorithm sketch looks reasonable.
Going to close this as a known quirk of the IL spec.