-
Notifications
You must be signed in to change notification settings - Fork 17.9k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
x/tools/go/ssa: wrong base pointer of loadconstraint when handling *ssa.Next in genInstr()@gen.go #45735
Comments
cc @findleyr |
cc @alandonovan is the original author of the package and probably understands this code the best. Fixing this requires understanding an edge case in the pointer package, in particular the constraint generation for (*ssa.Next) on maps. Below is a summary of what is happening. I am not yet confident I understand what needs to be fixed. I was able to reproduce the report following https://grpc.io/docs/languages/go/quickstart/. Here is what is happening in way too much detail. The instruction is:
Note the The local nodes are indeed as above (the constants differ from the original report):
At the end of the *ssa.Next case within genInstr() (line) the values of the following expressions are
From this we know the code took the else branch of We then enter
This means we fall into the
This then creates the anomalous load constraint in the reported issue:
n169141 is just The region All of that put together, it looks like (*ssa.Next) is trying to flatten the memory when the key is an invalid kind, but either:
Hopefully @alandonovan can give some direction on which of these (*ssa.Next) should be modeled as. |
follow upGood newsThe simple patch [1] below fixes the problem in the analysis of grpc and passes the unit tests in golang.org/x/tools/go/{pointer,ssa}. Bad newsPerformanceThe fix may generate more nodes and hence slow things down a bit. It doesn't seem substantial from the runs I tried, but it is a possibility. Coherence of *ssa.NextThe patch above keeps around some useless optimisations in constraint generation in pointer for *ssa.Next. There appear to be other problems with *ssa.Next types, such as the offsets in *ssa.Extract when a type is invalid, and perhaps flattening. Also, it looks like we need a test and documentation for a range over a string in the generation of constraints. SSA compatibilityThe fix [1] no longer allows invalid types for *ssa.Next resulting from ranges over maps. Perhaps we should consider What is the recommended process for changing package ssa in such a way? It's in x/tools, marked experimental in the docs, but it seems a number of tools depend on it as is. Not easily solvable in go/pointerAll attempts to fix the problem in go/pointer failed.
Conclusions@timothy-king it looks like almost all your alternatives for sources of incoherencies with the flattening are involved. (Note it looks like @alandonovan moved from Google to Github: we may need to fix and continue this without him? @matloob ?) It looks like this problem can be fixed in go/ssa/builder.go if the fix does not cause problems for the community. It also looks like the pointer analysis could have more extensive testing, and/or an internal consistency checks. Thoughts? References[1] Diff of a fix.
|
Please feel free to assign this issue to me if there are no other takers. |
Like other x/tools package changes, the recommended process is to discuss this over a GH issue. This is not a big enough change to warrant a proposal IMO. My quick summary of the proposed patch is to remove the following line from the documentation of *ssa.Next:
Strictly speaking this is not backwards compatible with the previous contract. It is possible to use this as a side-effect for detecting "_, x := range" statements. Though I doubt this is happening in practice. This is in the realm of a change I think we can consider.
I am not sure whether this is exactly right.
I am not yet seeing an explanation for the root cause of the bug in this list. This still looks like a bug in go/pointer. go/ssa does not look like it has a bug. There are an order of magnitude more users of go/ssa than go/pointer. At the moment, I am inclined to suggest finding the root cause in go/pointer over making a mildly backwards incompatible change to go/ssa. I am willing to update this opinion if we continue to be stumped.
We can address this without @alandonovan's input. (Would be nice though.) @findleyr is listed as the "Secondary" owner for x/tools/go/ssa and would be a natural 2nd pair of eyes to take a look at this change. (PS. It is kinda fun running into another VERIMAG alum.) |
Hi, yes I can definitely take a look -- in particular I can try to offer an opinion on compatibility issues. Let me catch up a bit, and comment later this week. |
(PS Indeed!) RE: summary of (previously) proposed change: yes, also for other range iters I would guess (at least string). As for the root cause, @timothy-king 's observation that the types of k, v can be different than the map type made me try another fix in go/pointer/gen.go [1], which is based on the idea that the root cause is the false assumption that k, v types are the same as the corresponding Map.Key(), Map.Elem(). It passes the unit tests and the erroneous grpc case looks ok too. I concur that the difference in usage of ssa vs pointer merits giving preference to a fix in pointer. [1]
|
I think the patch may be incomplete. |
Yes, done. |
Change https://golang.org/cl/335889 mentions this issue: |
This is my first CL for go or go/tools. What happens next? |
Hi @wsc0, I've submitted your CL. It is available immediately at master, and we tag x/tools ~occasionally, at which point more users will pick it up. Thanks for your contribution! |
Thanks @findleyr, it's my pleasure. |
What version of Go are you using (
go version
)?Does this issue reproduce with the latest release?
Yes.
What operating system and processor architecture are you using (
go env
)?go env
OutputWhat did you do?
Run go pointer analysis under the directory /grpc-go/examples/features/xds/client (master with commit e38032e927812bb354297adcab933bedeff6c177) to analyze the main.go file. I do not think the commit is a necessary, probably the code from recent master is also able to reproduce the issue. I used the program below to run pointer analysis:
What did you expect to see?
In the log, the constraints generated for IR statement
t40 = next t34
in function(*google.golang.org/grpc/xds/internal/balancer/edsbalancer.balancerGroup).close
should be:where n319631 (the base pointer of the load) is from "Creating nodes for local values":
What did you see instead?
Instead, the generated constraints are:
where n319634 is from a irrelevant local variable at the begging of this function:
I copied the grpc function here with which source code the above two IR statements mapped to:
So, why is the node for t40 replaced by the node for t4 in the generated constraints, if my understanding is correct?
I checked the source code a little bit, found that the wrong mapping is because of the computation of
odst += ksize
when generating constraints for *ssa.Next and the key type is invalid (the code is at go/pointer/gen.go:1078 of the most recent commit when I submit this issue). Should not this beodst += 1
? Because the algorithm only creates three pointers/nodes for this *ssa.Next instruction: ok, key and value. There is no flatten copy for key or value pointers. So, if the key type is invalid, shouldn't it skip this key node and use the value node (+= 1) as the load base, since the value will be extract later?Thanks.
The text was updated successfully, but these errors were encountered: