Discussion:
code review 14430048: cmd/5g, cmd/5l, cmd/6g, cmd/6l, cmd/8g, cmd/8l, cmd/gc,... (issue 14430048)
(too old to reply)
cshapiro-iFWiy5xATs8dnm+
2013-11-12 22:01:38 UTC
Permalink
Reviewers: golang-dev1,

Message:
Hello golang-dev-/***@public.gmane.org,

I'd like you to review this change to
https://code.google.com/p/go/


Description:
cmd/5g, cmd/5l, cmd/6g, cmd/6l, cmd/8g, cmd/8l, cmd/gc, runtime:
generate pointer maps by liveness analysis

This change allows the garbage collector to examine stack
slots that are determined as live and containing a pointer
value by the garbage collector. This results in a mean
reduction of 65% in the number of stack slots scanned during
an invocation of "GOGC=1 all.bash".

Unfortunately, this does not yet allow garbage collection to
be precise for the stack slots computed as live. Pointers
confound the determination of what definitions reach a given
instruction. In general, this problem is not solvable without
runtime cost but some advanced cooperation from the compiler
might mitigate common cases.

Please review this at https://codereview.appspot.com/14430048/

Affected files (+2050, -446 lines):
M src/cmd/5g/ggen.c
M src/cmd/5g/gsubr.c
M src/cmd/5g/opt.h
M src/cmd/5g/peep.c
M src/cmd/5g/prog.c
M src/cmd/5g/reg.c
M src/cmd/5l/5.out.h
M src/cmd/6g/ggen.c
M src/cmd/6g/gsubr.c
M src/cmd/6g/opt.h
M src/cmd/6g/prog.c
M src/cmd/6g/reg.c
M src/cmd/6l/6.out.h
M src/cmd/6l/optab.c
M src/cmd/8g/ggen.c
M src/cmd/8g/gsubr.c
M src/cmd/8g/opt.h
M src/cmd/8g/prog.c
M src/cmd/8g/reg.c
M src/cmd/8l/8.out.h
M src/cmd/8l/optab.c
M src/cmd/cc/pgen.c
M src/cmd/dist/build.c
A src/cmd/gc/array.c
M src/cmd/gc/bv.c
M src/cmd/gc/gen.c
M src/cmd/gc/go.h
M src/cmd/gc/pgen.c
A src/cmd/gc/plive.c
M src/pkg/runtime/funcdata.h
M src/pkg/runtime/mgc0.c
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
rsc-iFWiy5xATs8dnm+
2013-11-15 20:22:29 UTC
Permalink
Initial round of comments. I'm only a small part of the way into plive.c
and will keep reading after the weekend.



https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/gsubr.c
File src/cmd/5g/gsubr.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/gsubr.c#newcode255
src/cmd/5g/gsubr.c:255: Prog *result;
Please use names similar to the ones used by nearby functions.
It makes the file easier to scan if the conventions are not changing
from function to function.

s/result/p/
s/node/n/

You could also drop the return value entirely. The callers don't use it.

This function should move into ../gc/pgen.c, since it is the same on all
systems.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/opt.h
File src/cmd/5g/opt.h (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/opt.h#newcode191
src/cmd/5g/opt.h:191: Return = 1<<24, // return instruction
Delete.
Check for p->as == ARET instead. There's only one return instruction.
Code in pgen.c and popt.c already assumes this, so it is safe to depend
on.

Same for the other architectures.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/6l/optab.c
File src/cmd/6l/optab.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/6l/optab.c#newcode1355
src/cmd/6l/optab.c:1355: { ATYPE },
Are these new lines necessary? It seems like if ATYPE wasn't needed
before, it shouldn't be needed now.
And CHECKNIL and FATVARDEF should not be seen by the linker at all.
I think this file can be reverted.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/cc/pgen.c
File src/cmd/cc/pgen.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/cc/pgen.c#newcode39
src/cmd/cc/pgen.c:39: makefuncdatasym(char* namefmt, int64 funcdatakind)
s/char* /char */

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c
File src/cmd/gc/array.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c#newcode24
src/cmd/gc/array.c:24: Array* result;
s/Array* /Array */

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c#newcode112
src/cmd/gc/array.c:112: arrayindexof(Array* array, void *element)
s/Array* /Array */

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c#newcode126
src/cmd/gc/array.c:126: arraysort(Array* array, int (*cmp)(const void*,
const void*))
s/Array* /Array */

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c
File src/cmd/gc/bv.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c#newcode81
src/cmd/gc/bv.c:81: Bvec* dst;
s/Bvec* /Bvec */

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c#newcode149
src/cmd/gc/bv.c:149: bvres(Bvec *bv, int32 i)
s/res/reset or clear/
Took me a while to figure out what 'res' meant.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c#newcode160
src/cmd/gc/bv.c:160: bvresall(Bvec *bv)
Same.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/pgen.c
File src/cmd/gc/pgen.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/pgen.c#newcode18
src/cmd/gc/pgen.c:18: makefuncdatasym(char* namefmt, int64 funcdatakind)
s/char* /char */

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode29
src/cmd/gc/plive.c:29: // control flow graph, the opt member will be
nil.
maybe this is a good place to say how the chaining works.

// First and last instructions in the block.
// Within the block, p->link points to the next instruction
// and p->opt points to the previous instruction.
// The first instruction's p->opt == nil.
// The last instruction's p->link points at the next instruction
// in the function (outside the block).
//
// To walk forward over the block:
// for(p = bb->first;; p = p->link) {
// ...
// if(p == bb->last)
// break;
// }
//
// To walk backward over the block:
// for(p = bb->last; p != nil; p = p->opt) {
// ...
// }
Prog *first;
Prog *last;

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode30
src/cmd/gc/plive.c:30: Prog* first;
s/* / */
about 20x in this file

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode46
src/cmd/gc/plive.c:46: typedef struct BasicBlock BasicBlock;
move above struct definition, to match code elsewhere in compiler.
same for Liveness.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode155
src/cmd/gc/plive.c:155: for(i = 0; i < arraylength(bb->pred); i++) {
I assume this code is disabled because it doesn't work.

It doesn't work because the code assumes that the previous instruction
in the linear instruction stream must be from a predecessor of the basic
block. That's not true. If the code looks like

JNE x
...
RET
x:
FOO

Then inserting before FOO will need to find the RET to insert properly
into the instruction stream, and but the block containing that RET is
not one of the basic block predecessors of the block beginning at x. The
same would happen with a JMP.

To avoid iterating over the entire instruction list to find the RET, I
think the solution is for each BasicBlock to record the Prog* that
precedes it in the instruction stream. It is not possible to derive that
pointer from the ordinary basic block predecessors.

The same assumption is present in the comment on Prog *last above, where
it says "will point to a fall through instruction". That's not always
true, at least if you consider RET not to fall through to label x above.
I cleaned that up in the text I suggested.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode207
src/cmd/gc/plive.c:207: // are two critera for termination. If the end
of basic block is reached a
criteria

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode209
src/cmd/gc/plive.c:209: // iteration is stopped and the value of the
predicate is returned upward.
s/ upward//

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode224
src/cmd/gc/plive.c:224: // Collects and returns the nodes for functions
arguments and local variables.
For each function taking or returning an Array*, please say the type of
the array element in the comment.


// Returns an array of Node*s.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode245
src/cmd/gc/plive.c:245: // A pretty printer for control flow graphs.
... for a control flow graph, an array of BasicBlock*s.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode272
src/cmd/gc/plive.c:272: *rpo -= 1;
--

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode333
src/cmd/gc/plive.c:333: if(iscall(prog, "runtime", names[i]))
Typically the way to do this is to make an array of the symbols involved
and then check

if(p->as == ACALL && p->to.sym == sym[i])

The repeated strcmps are not necessary because there is only one symbol
for a given (path, name) pair.
See the noreturn function in popt.c.

Same applies to isnewselect and isselectgocall.

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c#newcode1348
src/pkg/runtime/mgc0.c:1348: getstackmapdata(StackMap *stackmap, int32
n)
s/get//

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c#newcode1433
src/pkg/runtime/mgc0.c:1433: targetpc -= 1;
targetpc--

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c#newcode1435
src/pkg/runtime/mgc0.c:1435: if(pcdata == -1)
please use { } around multiline bodies, even if it's just a big comment
+ one statement

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
cshapiro-iFWiy5xATs8dnm+
2013-11-16 02:00:16 UTC
Permalink
still need to clean-up some comments...


https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/gsubr.c
File src/cmd/5g/gsubr.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/gsubr.c#newcode255
src/cmd/5g/gsubr.c:255: Prog *result;
Post by rsc-iFWiy5xATs8dnm+
Please use names similar to the ones used by nearby functions.
It makes the file easier to scan if the conventions are not changing
from
Post by rsc-iFWiy5xATs8dnm+
function to function.
s/result/p/
s/node/n/
You could also drop the return value entirely. The callers don't use
it.
Post by rsc-iFWiy5xATs8dnm+
This function should move into ../gc/pgen.c, since it is the same on
all
Post by rsc-iFWiy5xATs8dnm+
systems.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/opt.h
File src/cmd/5g/opt.h (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/5g/opt.h#newcode191
src/cmd/5g/opt.h:191: Return = 1<<24, // return instruction
Post by rsc-iFWiy5xATs8dnm+
Delete.
Check for p->as == ARET instead. There's only one return instruction.
Code in pgen.c and popt.c already assumes this, so it is safe to
depend on.
Post by rsc-iFWiy5xATs8dnm+
Same for the other architectures.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/6l/optab.c
File src/cmd/6l/optab.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/6l/optab.c#newcode1355
src/cmd/6l/optab.c:1355: { ATYPE },
Different backends have different consistency checks for instructions in
this table. Notably, whether the offset agrees with the instruction.
It makes it a lot easier to add an instruction across all the ports when
you list them out explicitly.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c
File src/cmd/gc/array.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c#newcode24
src/cmd/gc/array.c:24: Array* result;
Post by rsc-iFWiy5xATs8dnm+
s/Array* /Array */
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c#newcode112
src/cmd/gc/array.c:112: arrayindexof(Array* array, void *element)
Post by rsc-iFWiy5xATs8dnm+
s/Array* /Array */
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/array.c#newcode126
src/cmd/gc/array.c:126: arraysort(Array* array, int (*cmp)(const void*,
const void*))
Post by rsc-iFWiy5xATs8dnm+
s/Array* /Array */
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c
File src/cmd/gc/bv.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c#newcode81
src/cmd/gc/bv.c:81: Bvec* dst;
Post by rsc-iFWiy5xATs8dnm+
s/Bvec* /Bvec */
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c#newcode149
src/cmd/gc/bv.c:149: bvres(Bvec *bv, int32 i)
Post by rsc-iFWiy5xATs8dnm+
s/res/reset or clear/
Took me a while to figure out what 'res' meant.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/bv.c#newcode160
src/cmd/gc/bv.c:160: bvresall(Bvec *bv)
Post by rsc-iFWiy5xATs8dnm+
Same.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/pgen.c
File src/cmd/gc/pgen.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/pgen.c#newcode18
src/cmd/gc/pgen.c:18: makefuncdatasym(char* namefmt, int64 funcdatakind)
Post by rsc-iFWiy5xATs8dnm+
s/char* /char */
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode30
src/cmd/gc/plive.c:30: Prog* first;
Post by rsc-iFWiy5xATs8dnm+
s/* / */
about 20x in this file
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode46
src/cmd/gc/plive.c:46: typedef struct BasicBlock BasicBlock;
Post by rsc-iFWiy5xATs8dnm+
move above struct definition, to match code elsewhere in compiler.
same for Liveness.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode155
src/cmd/gc/plive.c:155: for(i = 0; i < arraylength(bb->pred); i++) {
No, this code is out of context. (I used to break the forward links at
a block boundary and reassemble the blocks in a single pass afterward.
Now the links are left as-is. I actually prefer the reassembly
approach.)

I have a simpler workaround for the splicing issue which involves
swapping the instruction with a prog and appending a copy afterward.
That makes the splicing operation local.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode207
src/cmd/gc/plive.c:207: // are two critera for termination. If the end
of basic block is reached a
Post by rsc-iFWiy5xATs8dnm+
criteria
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode209
src/cmd/gc/plive.c:209: // iteration is stopped and the value of the
predicate is returned upward.
I'm not sure what the issue is here. You will have to explain further.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode272
src/cmd/gc/plive.c:272: *rpo -= 1;
(*rpo)--; is a lot more syntax than *rpo -= 1; I think the latter is
cleaner than the former.

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c#newcode1348
src/pkg/runtime/mgc0.c:1348: getstackmapdata(StackMap *stackmap, int32
n)
Post by rsc-iFWiy5xATs8dnm+
s/get//
Done.

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c#newcode1433
src/pkg/runtime/mgc0.c:1433: targetpc -= 1;
Post by rsc-iFWiy5xATs8dnm+
targetpc--
Done.

https://codereview.appspot.com/14430048/diff/160001/src/pkg/runtime/mgc0.c#newcode1435
src/pkg/runtime/mgc0.c:1435: if(pcdata == -1)
Post by rsc-iFWiy5xATs8dnm+
please use { } around multiline bodies, even if it's just a big
comment + one
Post by rsc-iFWiy5xATs8dnm+
statement
Done.

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
rsc-iFWiy5xATs8dnm+
2013-11-18 21:19:31 UTC
Permalink
https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode155
src/cmd/gc/plive.c:155: for(i = 0; i < arraylength(bb->pred); i++) {
Post by cshapiro-iFWiy5xATs8dnm+
No, this code is out of context. (I used to break the forward links
at a block
Post by cshapiro-iFWiy5xATs8dnm+
boundary and reassemble the blocks in a single pass afterward. Now
the links
Post by cshapiro-iFWiy5xATs8dnm+
are left as-is. I actually prefer the reassembly approach.)
I have a simpler workaround for the splicing issue which involves
swapping the
Post by cshapiro-iFWiy5xATs8dnm+
instruction with a prog and appending a copy afterward. That makes
the splicing
Post by cshapiro-iFWiy5xATs8dnm+
operation local.
Great.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode209
src/cmd/gc/plive.c:209: // iteration is stopped and the value of the
predicate is returned upward.
Post by cshapiro-iFWiy5xATs8dnm+
I'm not sure what the issue is here. You will have to explain
further.

Upward is an unusual thing to say - I don't think of function calls as
having directions. And assuming I understand that upward means "to the
caller", "returned upward" is redundant. "returned" is just as good.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode272
src/cmd/gc/plive.c:272: *rpo -= 1;
Post by cshapiro-iFWiy5xATs8dnm+
(*rpo)--; is a lot more syntax than *rpo -= 1; I think the latter is
cleaner
Post by cshapiro-iFWiy5xATs8dnm+
than the former.
OK.

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
cshapiro-iFWiy5xATs8dnm+
2013-11-18 22:21:54 UTC
Permalink
PTAL


https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode29
src/cmd/gc/plive.c:29: // control flow graph, the opt member will be
nil.
Post by rsc-iFWiy5xATs8dnm+
maybe this is a good place to say how the chaining works.
// First and last instructions in the block.
// Within the block, p->link points to the next instruction
// and p->opt points to the previous instruction.
// The first instruction's p->opt == nil.
// The last instruction's p->link points at the next instruction
// in the function (outside the block).
//
// for(p = bb->first;; p = p->link) {
// ...
// if(p == bb->last)
// break;
// }
//
// for(p = bb->last; p != nil; p = p->opt) {
// ...
// }
Prog *first;
Prog *last;
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode224
src/cmd/gc/plive.c:224: // Collects and returns the nodes for functions
arguments and local variables.
Post by rsc-iFWiy5xATs8dnm+
For each function taking or returning an Array*, please say the type
of the
Post by rsc-iFWiy5xATs8dnm+
array element in the comment.
// Returns an array of Node*s.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode245
src/cmd/gc/plive.c:245: // A pretty printer for control flow graphs.
Post by rsc-iFWiy5xATs8dnm+
... for a control flow graph, an array of BasicBlock*s.
Done.

https://codereview.appspot.com/14430048/diff/160001/src/cmd/gc/plive.c#newcode333
src/cmd/gc/plive.c:333: if(iscall(prog, "runtime", names[i]))
Post by rsc-iFWiy5xATs8dnm+
Typically the way to do this is to make an array of the symbols
involved and
Post by rsc-iFWiy5xATs8dnm+
then check
if(p->as == ACALL && p->to.sym == sym[i])
The repeated strcmps are not necessary because there is only one
symbol for a
Post by rsc-iFWiy5xATs8dnm+
given (path, name) pair.
See the noreturn function in popt.c.
Same applies to isnewselect and isselectgocall.
Done.

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
rsc-iFWiy5xATs8dnm+
2013-11-19 15:16:49 UTC
Permalink
[made it through progeffects. almost halfway.]

What is the plan for getting from here to precise collection?
The last time we talked I thought it would be to identify the few
ambiguously live places on the stack and zero them on entry.



https://codereview.appspot.com/14430048/diff/220001/src/cmd/dist/build.c
File src/cmd/dist/build.c (right):

https://codereview.appspot.com/14430048/diff/220001/src/cmd/dist/build.c#newcode455
src/cmd/dist/build.c:455: "-O0",
revert

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode51
src/cmd/gc/plive.c:51: // fall through instruction or nil, if this is
the last instruction in
This is still incorrect, at least for the usual definition of "fall
through".
I would just delete this sentence entirely. The meaning of link here is
unchanged from the rest of the compiler.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode215
src/cmd/gc/plive.c:215: blockany(BasicBlock *bb, int (*pred)(Prog*))
pred is pretty confusing here. everywhere else in the file pred means
predecessor.
maybe s/predicate/function/ and s/pred/f/?
it is particularly confusing in some of the calls to blockany which read
blockany(pred, xxx), with pred in the "wrong" place.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode229
src/cmd/gc/plive.c:229: // variables. Returns an array of Node*s.
can drop second sentence, since it is also in the first sentence.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode394
src/cmd/gc/plive.c:394: if(blockany(pred, isnewselect))
{ }

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode583
src/cmd/gc/plive.c:583: if(!strcmp(node->sym->name, names[i]))
please use strcmp == 0.
that's the idiom everywhere else in the tree.
! is too easy to misread as 'not equal', which is the wrong sense.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode589
src/cmd/gc/plive.c:589: // variables. The vars argument is an array of
Nodes*s.
s/Nodes/Node/

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode606
src/cmd/gc/plive.c:606: // sake of backtrace quality, we read in
arguments as well.
Can you elaborate about this 'backtrace quality' issue?

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode615
src/cmd/gc/plive.c:615: // Because the lifetime of stack temporaries
s/temporaries/variables/

the actual temporaries, in the sense used in the rest of the compiler,
usually do have a clear lifetime.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode625
src/cmd/gc/plive.c:625: if((info.flags & Pseudo) && (prog->as == ATEXT))
{
drop unnecessary ( ) around ==
also you could drop the Pseudo thing entirely.
if(prog->as == ATEXT) {

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode647
src/cmd/gc/plive.c:647: if((info.flags & LeftRead) || (info.flags &
LeftAddr))
if(info.flags & (LeftRead | LeftAddr))

same, just matches the other tests in this file

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode665
src/cmd/gc/plive.c:665: if((info.flags & RightRead) || (info.flags &
RightAddr))
if(info.flags & (RightRead | RightAddr))

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
rsc-iFWiy5xATs8dnm+
2013-11-19 16:48:59 UTC
Permalink
got through livenessprintcfg. more meetings



https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode820
src/cmd/gc/plive.c:820: // out[b] = U s E succ[b], in[s]
What does "U s E" mean?
I assume it is some kind of mathematical notation, probably a union, but
I can't figure out how "s E" factors in in.
English would probably be better.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode843
src/cmd/gc/plive.c:843: // Prints a binary representation of a machine
word.
Delete. Use %032b below.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1458
src/cmd/gc/plive.c:1458: print("twobitwritesymbol: expected ");
print("twobitwritesymbol: expected %032b to be a subset of %032b\n",
word, checkword);

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
rsc-iFWiy5xATs8dnm+
2013-11-19 19:04:13 UTC
Permalink
https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode764
src/cmd/gc/plive.c:764: static void
Needs a comment about what is going on here.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode765
src/cmd/gc/plive.c:765: livenessprologue(Liveness *lv)
Can livenessprologue and livenesssolve move down nearer to
livenessepilogue? Right now there is a large chunk of printing and
debugging code between them.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode942
src/cmd/gc/plive.c:942: static void
add comment about what this checks.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode946
src/cmd/gc/plive.c:946: int found = 0;
please declare variables at top of function, to match rest of code base.
x8

also, this code is nearly exactly the same as the p->to.type == D_AUTO
case. it seems like this function should be

static void
checkprog(Node *fn, Prog *p)
{
if(p->from.type == D_AUTO)
checkauto(p->from.node);
if(p->from.type == D_PARAM)
checkparam(p->from.node);
if(p->to.type == D_AUTO)
checkauto(p->to.node);
if(p->to.type == D_PARAM)
checkparam(p->to.node);
}

and then all the found variables go away entirely, since the check
functions can just return.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1143
src/cmd/gc/plive.c:1143: for(i = 0; i < t->bound; ++i)
i++ please, to match rest of code base

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1207
src/cmd/gc/plive.c:1207: // In various and obscure circumstances the
this argument and in
It would be more helpful to write down what the circumstances are.
What code caused it to happen? Given that, perhaps I will be able to say
what the conditions are.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1225
src/cmd/gc/plive.c:1225: // any type are are tracked, not just pointers.
The this argument and the in
s/are are/are/

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1296
src/cmd/gc/plive.c:1296: naddr(&from, &pcdata->from, 1);
s/1/0/ & on next line too
(Given that this is constructing a "disembodied" prog, it seems a
mistake to set naddr's canemitcode parameter to 1.)

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1309
src/cmd/gc/plive.c:1309: // Visits all
Needs a better comment.

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1358
src/cmd/gc/plive.c:1358: if(pos < 0)
{ }

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1405
src/cmd/gc/plive.c:1405: // Record dead values.
Should this be behind some kind of debug flag?

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode1442
src/cmd/gc/plive.c:1442: if(len > 0) {
delete. no performance impact and will remove an indentation level from
already very-indented code.

https://codereview.appspot.com/14430048/diff/220001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

https://codereview.appspot.com/14430048/diff/220001/src/pkg/runtime/mgc0.c#newcode1436
src/pkg/runtime/mgc0.c:1436: // We do not have a valid pcdata value but
there might be a
This comment is a bit pessimistic. It seems that the actual situation is

// pcdata==-1 means either we have not started executing the function
yet
// or it does not have stack frame maps. If the funcdata load below
succeeds,
// it must be the former: the function has not started and has no stack
frame.
// The information for that state is in stack map index slot 0.

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Russ Cox
2013-11-20 19:18:18 UTC
Permalink
I patched this CL into a fresh client, and I believe the information is too
conservative for variables that have their address taken. Specifically,
consider this program (http://play.golang.org/p/Km_aIP2sRa):

1 package main
2
3 var b, b1 = true, true
4
5 func main() {
6 if b1 {
7 var x **int
8 if b {
9 y := h(1)
10 x = &y
11 } else {
12 z := h(2)
13 x = &z
14 }
15 h(3)
16 pr(x)
17 return
18 }
19 g()
20 }
21
22 func g() {}
23
24 func h(z int) *int { return &z }
25
26 func pr(x **int) { println(x, *x, **x) }
23 func h() *int
24
25 func pr(**int)

The taking of y's address at line 10 and z's address at line 13 creates the
situation at line 15 where exactly one of y or z is live and initialized
(and pointed to by x). The other is uninitialized and should be ignored
during a garbage collection at the call to pr. Since the liveness analysis
cannot express this, it must conservatively mark both y and z as live, and
it does. However, it also marks them live at the call to g. There is no
control flow from lines 10 or 13 to the call of g at line 19, so marking y
and z as live is unnecessary there. Only code reachable from the taking of
an address of a variable - or, if it's easier, the declaration of the
variable - should be considered to use the variable.

The basic block dump for this program is below. It is basic block 5 that is
being too pessimistic, listing z^@ and y^@ in uevar and livein. I am
compiling with -l to disable inlining to streamline the code.

Russ

basic block 0
pred:
succ: 5 1
uevar:
varkill:
livein: z^@ y^@
liveout: z^@ y^@
prog:
0000 (/Users/rsc/x3.go:5) TEXT main+0(SB),$0-0
0001 (/Users/rsc/x3.go:5) FUNCDATA $2,gcargs·0+0(SB)
0002 (/Users/rsc/x3.go:5) FUNCDATA $3,gclocals·1+0(SB)
0003 (/Users/rsc/x3.go:5) FUNCDATA $4,gcdead·2+0(SB)
0004 (/Users/rsc/x3.go:5) TYPE x+-24(SP){**int},$8
0005 (/Users/rsc/x3.go:5) TYPE y+-16(SP){*int},$8
0006 (/Users/rsc/x3.go:5) TYPE z+-8(SP){*int},$8
0008 (/Users/rsc/x3.go:5) TYPE autotmp_0002+0(SP){*int},$8
0011 (/Users/rsc/x3.go:6) CMPB b1+0(SB),$0
0012 (/Users/rsc/x3.go:6) JEQ ,42
basic block 1
pred: 0
succ: 3 2
uevar:
varkill:
livein: z^@ y^@
liveout: z^@ y^@
prog:
0016 (/Users/rsc/x3.go:8) CMPB b+0(SB),$0
0017 (/Users/rsc/x3.go:8) JEQ ,27
basic block 2
pred: 1
succ: 4
uevar:
varkill: y^@ x^
livein: z^@
liveout: z^@ y^@ x^
prog:
0018 (/Users/rsc/x3.go:9) MOVQ $1,(SP)
0019 (/Users/rsc/x3.go:9) CALL ,h+0(SB)
0020 (/Users/rsc/x3.go:9) MOVQ 8(SP),BX
0023 (/Users/rsc/x3.go:9) MOVQ BX,y+-16(SP)
0024 (/Users/rsc/x3.go:10) LEAQ y+-16(SP),BX
0025 (/Users/rsc/x3.go:10) MOVQ BX,x+-24(SP)
0026 (/Users/rsc/x3.go:8) JMP ,35
basic block 3
pred: 1
succ: 4
uevar:
varkill: z^@ x^
livein: y^@
liveout: z^@ y^@ x^
prog:
0027 (/Users/rsc/x3.go:12) MOVQ $2,(SP)
0028 (/Users/rsc/x3.go:12) CALL ,h+0(SB)
0029 (/Users/rsc/x3.go:12) MOVQ 8(SP),BX
0032 (/Users/rsc/x3.go:12) MOVQ BX,z+-8(SP)
0033 (/Users/rsc/x3.go:13) LEAQ z+-8(SP),BX
0034 (/Users/rsc/x3.go:13) MOVQ BX,x+-24(SP)
basic block 4
pred: 3 2
succ:
uevar: z^@ y^@ x^
varkill:
livein: z^@ y^@ x^
liveout:
prog:
0035 (/Users/rsc/x3.go:15) MOVQ $3,(SP)
0036 (/Users/rsc/x3.go:15) CALL ,h+0(SB)
0037 (/Users/rsc/x3.go:16) MOVQ x+-24(SP),BX
0038 (/Users/rsc/x3.go:16) MOVQ BX,(SP)
0039 (/Users/rsc/x3.go:16) CALL ,pr+0(SB)
0040 (/Users/rsc/x3.go:17) RET ,
basic block 5
pred: 0
succ:
uevar: z^@ y^@
varkill:
livein: z^@ y^@
liveout:
prog:
0042 (/Users/rsc/x3.go:19) CALL ,g+0(SB)
0043 (/Users/rsc/x3.go:20) RET ,
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Carl Shapiro
2013-11-20 22:34:53 UTC
Permalink
Post by Russ Cox
The taking of y's address at line 10 and z's address at line 13 creates
the situation at line 15 where exactly one of y or z is live and
initialized (and pointed to by x). The other is uninitialized and should be
ignored during a garbage collection at the call to pr. Since the liveness
analysis cannot express this, it must conservatively mark both y and z as
live, and it does.
The assumption you are making about why variables are marked live is not
correct. The variables y and z are marked as live because their address is
taken. The liveness analysis only understands when a variable is read or
written. It does not understand anything else including, but not limited
to, assignments, scopes, or points-to relationships. Therefore, it must
conservatively assume that when the address of a variable is exposed, that
address can be stored into another variable with a greater lifetime.

However, it also marks them live at the call to g. There is no control flow
Post by Russ Cox
from lines 10 or 13 to the call of g at line 19, so marking y and z as live
is unnecessary there. Only code reachable from the taking of an address of
a variable - or, if it's easier, the declaration of the variable - should
be considered to use the variable.
This is because once an address is taken, it is considered downward live.
It must be considered so because is possible for the address to escape
into another variable. The liveness analysis only knows about the
existence of reads and writes to variable. It does not know anything that
it could use to prove otherwise.

In the current scheme, the stack maps encode live pointers and all of their
potential referents. I implemented this specific behavior at your request
because you felt my original scheme did not support the stack growing
algorithm and that this encoding would. My originally scheme only included
the live pointers in liveness bitmap and relied on the garbage collector,
instead of the compiler, to find any referents in the stack.

I still do not believe that encoding the referents in the bitmap is the
best approach, irrespective of any effect on stack growing. However, I was
not able to convince you otherwise and I so agreed to go along with this
decision since you agreed to implement the zeroing.
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Russ Cox
2013-11-21 00:21:19 UTC
Permalink
Post by Carl Shapiro
Post by Russ Cox
The taking of y's address at line 10 and z's address at line 13 creates
the situation at line 15 where exactly one of y or z is live and
initialized (and pointed to by x). The other is uninitialized and should be
ignored during a garbage collection at the call to pr. Since the liveness
analysis cannot express this, it must conservatively mark both y and z as
live, and it does.
The assumption you are making about why variables are marked live is not
correct. The variables y and z are marked as live because their address is
taken. The liveness analysis only understands when a variable is read or
written. It does not understand anything else including, but not limited
to, assignments, scopes, or points-to relationships. Therefore, it must
conservatively assume that when the address of a variable is exposed, that
address can be stored into another variable with a greater lifetime.
I'm sorry, but I don't understand where I'm going wrong. These are the
assumptions I am making:

The liveness analysis has a full control flow graph.

A variable's address cannot be taken before it is initialized; more
generally, it is impossible for a variable's address to be taken without
mentioning the variable in an instruction.

The liveness analysis can tell which safe points are reachable from the
initialization (or, equivalently, from any mention) of the variable.

Only those safe points need to treat the variable as live.

That leads me to this conclusion:

In the current CL, all RET instruction safe points treat the variable as
live, not just the ones that are reachable from the variable's definition.
This is unnecessary.

If you disagree with this conclusion, can you tell me which assumption or
logical step is wrong?

However, it also marks them live at the call to g. There is no control flow
Post by Carl Shapiro
Post by Russ Cox
from lines 10 or 13 to the call of g at line 19, so marking y and z as live
is unnecessary there. Only code reachable from the taking of an address of
a variable - or, if it's easier, the declaration of the variable - should
be considered to use the variable.
This is because once an address is taken, it is considered downward live.
It must be considered so because is possible for the address to escape
into another variable. The liveness analysis only knows about the
existence of reads and writes to variable. It does not know anything that
it could use to prove otherwise.
What is the meaning of "downward" here? To me, downward from X means things
reachable from X in the control flow graph. But that's not what the current
version of the CL does. For example, the code I posted earlier is
equivalent to this code:

1 func main() {
2 if !b1 {
3 g()
4 return
5 }
6 var x **int
7 if b {
8 y := h(1)
9 x = &y
10 } else {
11 z := h(2)
12 x = &z
13 }
14 h(3)
15 pr(x)
16 return
17 }

My concern with the current CL's semantics is that it treats all variables
with an address taken as live at every return statement. Concretely, it
treats y (line 8) and z (line 11) as live at the return statement on line
4. In what sense is line 4 "downward" from lines 8 and 11?
Post by Carl Shapiro
In the current scheme, the stack maps encode live pointers and all of
their potential referents. I implemented this specific behavior at your
request because you felt my original scheme did not support the stack
growing algorithm and that this encoding would. My originally scheme only
included the live pointers in liveness bitmap and relied on the garbage
collector, instead of the compiler, to find any referents in the stack.
I don't believe that is as simple as it sounds, but let's not get
sidetracked by that.
Post by Carl Shapiro
I still do not believe that encoding the referents in the bitmap is the
best approach, irrespective of any effect on stack growing. However, I was
not able to convince you otherwise and I so agreed to go along with this
decision since you agreed to implement the zeroing.
I am still willing to implement the zeroing, but I believe the liveness
analysis is the best place to decide what needs to be zeroed, because they
must be in sync. Fifteen minutes before you sent your message, I sent a
mail to the thread explaining how the liveness analysis in this CL can be
extended to decide what needs zeroing, giving both a description of the
algorithm and an implementation. Unless it is incorrect, it seems a simple,
straightforward way to get the information we need.

Thanks.
Russ
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Carl Shapiro
2013-11-21 01:57:53 UTC
Permalink
Post by Russ Cox
In the current CL, all RET instruction safe points treat the variable as
live, not just the ones that are reachable from the variable's definition.
This is unnecessary.
If you disagree with this conclusion, can you tell me which assumption or
logical step is wrong?
There is nothing wrong with your conclusion here.

The reading of variables with their address taken by ARET is something done
irrespective of the return instruction's placement relative to variable's
definition point. When I made this change for you I noted that such
overestimates can be cleaned up with an earlier reaching definitions pass.
I am still fine with that.
Post by Russ Cox
My concern with the current CL's semantics is that it treats all variables
with an address taken as live at every return statement. Concretely, it
treats y (line 8) and z (line 11) as live at the return statement on line
4. In what sense is line 4 "downward" from lines 8 and 11?
I don't think there is a disagreement about effect, just the mechanism.
Post by Russ Cox
I don't believe that is as simple as it sounds, but let's not get
sidetracked by that.
This is the first time I am hearing that my original solution was not
simple. Originally, you claimed it was not correct. As far as I can tell,
this is the simpler and correct solution to the problem. Furthermore, it
is much more accurate than what you are proposing and has no runtime
overhead. If we are trying to make the best change to the compiler and
runtime, I would like to know why you still perceive zeroing to be better.
Post by Russ Cox
I am still willing to implement the zeroing, but I believe the liveness
analysis is the best place to decide what needs to be zeroed, because they
must be in sync. Fifteen minutes before you sent your message, I sent a
mail to the thread explaining how the liveness analysis in this CL can be
extended to decide what needs zeroing, giving both a description of the
algorithm and an implementation. Unless it is incorrect, it seems a simple,
straightforward way to get the information we need.
You need more than a signal that a condition exists. You need to generate
code to do something about it. The conditions that give rise to the
ambiguity in the first place can be resolved in the front end by moving the
resolved variable definitions with their address taken to an outer scope.
This can be done directly in an AST walk.

We already know zeroing is costly. To minimize the amount of zeroing
effort, the value flow in the AST can be used as a signal to understand if
zeroing is needed at all. Consider the following case

1 f() {
2 if (...) {
3 var x = ...
4 p := &x
5 g(p)
6 }
7 if (...) {
8 var y = ...
9 q := &y
10 h(q)
11 }
12 runtime.GC()
13 }

With your proposal, x would have to be zeroed between lines 1 and 2, and y
would have to be zeroed between lines 6 and 7. There is no reason for
either because the addresses of x and y never escape their scope. You
cannot know such information in the current implementation of liveness
analysis.

As is, your proposal has to recover information known upstream and
introduce a new way to transform the instruction stream rather than reuse
the mechanisms already present upstream. These are a strong indications
that the analysis and transformations in your proposal should be done
elsewhere.
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Russ Cox
2013-11-21 04:19:09 UTC
Permalink
Post by Russ Cox
I don't believe that is as simple as it sounds, but let's not get
Post by Russ Cox
sidetracked by that.
This is the first time I am hearing that my original solution was not
simple....
This is not relevant to the code in the CL. I'm happy to discuss this in a
separate thread or off list, but I don't want to sidetrack this CL review.

I am still willing to implement the zeroing, but I believe the liveness
Post by Russ Cox
Post by Russ Cox
analysis is the best place to decide what needs to be zeroed, because they
must be in sync. Fifteen minutes before you sent your message, I sent a
mail to the thread explaining how the liveness analysis in this CL can be
extended to decide what needs zeroing, giving both a description of the
algorithm and an implementation. Unless it is incorrect, it seems a simple,
straightforward way to get the information we need.
You need more than a signal that a condition exists. You need to generate
code to do something about it.
Here is what to do about it: set n->needzero = 1 and revert the changes
this CL makes to ggen.c's defframe function, and then that variable will be
zeroed on function entry.

The conditions that give rise to the ambiguity in the first place can be
Post by Russ Cox
resolved in the front end by moving the resolved variable definitions with
their address taken to an outer scope. This can be done directly in an AST
walk.
There is nothing in the front end that computes reaching definitions.
Placing each stack variable in its own slot in the frame avoids any need to
do so. It is certainly possible to add a phase to the front end to build a
control flow graph and use that graph to compute reaching definitions. The
liveness analysis in this CL has already built such a control flow graph,
however, and it is very easy - under 200 lines of code - to use that graph
to get the information we need. I don't understand the objection to doing
so. Even more importantly, using the same control flow analysis for the
stack liveness bitmaps and for the decision about what needs zeroing means
that the two pieces of data are guaranteed to be in sync with each other.

We already know zeroing is costly.
No, we know that zeroing every variable with pointers is too costly. We
explored doing that as a stopgap until the code computing stack maps (this
CL) was ready. With stack maps, only these ambiguously live variables need
to be zeroed.

In my earlier message in this thread - the one with a rough implementation
of what I am suggesting - I included a list of all the variables in the
standard tree that appear to need zeroing if we use stack maps. There are
24 such variables in the entire code base (and at least one is a false
positive, as my message explained). I think it is safe to say that
inserting 24 zeroings across the entire tree will not be too costly, and I
also think it is safe to say that typical code outside the standard tree
will not be significantly different in this regard.
Post by Russ Cox
To minimize the amount of zeroing effort, the value flow in the AST can
be used as a signal to understand if zeroing is needed at all. Consider
the following case
1 f() {
2 if (...) {
3 var x = ...
4 p := &x
5 g(p)
6 }
7 if (...) {
8 var y = ...
9 q := &y
10 h(q)
11 }
12 runtime.GC()
13 }
With your proposal, x would have to be zeroed between lines 1 and 2, and y
would have to be zeroed between lines 6 and 7. There is no reason for
either because the addresses of x and y never escape their scope. You
cannot know such information in the current implementation of liveness
analysis.
If g and h do not let the pointer argument escape to the heap, then yes my
current suggestion would be that the liveness analysis mark both x and y
with needzero = 1, causing them to be zeroed on function entry. Unless my
analysis has a bug, though, this doesn't come up much in real Go code (see
above).

As is, your proposal has to recover information known upstream and
Post by Russ Cox
introduce a new way to transform the instruction stream rather than reuse
the mechanisms already present upstream. These are a strong indications
that the analysis and transformations in your proposal should be done
elsewhere.
There is no new transformation of the instruction stream. The code is
already in ggen.c (except that this CL proposes to delete it). All the code
in plive.c needs to do is set the needzero flag on the relevant Node*s.

It is easy to wish things were different in earlier stages of the compiler,
but they are what they are. To make the collection of Go frames precise, we
need a certain analysis, and it is very easy to adjust the code in this CL
to perform that analysis.

Will you please add the analysis I am suggesting to this CL?

Thanks.
Russ
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Carl Shapiro
2013-11-22 02:00:55 UTC
Permalink
Post by Russ Cox
This is not relevant to the code in the CL. I'm happy to discuss this in a
separate thread or off list, but I don't want to sidetrack this CL review.
Sorry, this is very relevant to the code in this CL. The changes you are
asking for (including the address taken change I already implemented)
breaks the precision invariant I am trying to establish. The greater goal
is to make the stack scanner type-precise and liveness-precise. What you
are asking for means we are not liveness precise, and that directly
conflicts with what I have set out to do.

Liveness imprecision is very hard on users. It is difficult for users to
reason about. Because of that, users cannot be confident about their space
usage. Moreover, because Go has escape analysis, liveness imprecision
makes space complexity of programs vary depending on whether escape
analysis kicks in or not. You can end up using more space if objects with
heap referents get stack allocated.

Whether or not these problems appear frequent by static analysis really
does not matter to the person with a server that explodes in production
because of a space leak caused by liveness imprecision. The triage of
these bugs and the fix is not straightforward either. Liveness imprecision
has been a problem demonstrated time and again in other systems and by
going down this path we are inviting the same problem.

I am trying to avoid this problem. You need to explain why it is a good
idea to take a different approach and remain exposed to it.

There is nothing in the front end that computes reaching definitions.
Post by Russ Cox
Placing each stack variable in its own slot in the frame avoids any need to
do so. It is certainly possible to add a phase to the front end to build a
control flow graph and use that graph to compute reaching definitions. The
liveness analysis in this CL has already built such a control flow graph,
however, and it is very easy - under 200 lines of code - to use that graph
to get the information we need. I don't understand the objection to doing
so. Even more importantly, using the same control flow analysis for the
stack liveness bitmaps and for the decision about what needs zeroing means
that the two pieces of data are guaranteed to be in sync with each other.
Assuming we want to encode pointers and their potential referents in the
stack map, I do not believe the infrastructure you are referring to is
needed. The condition that gives rise to this situation are values
escaping their scope. This condition is only possible with escape analysis
turned on. The existence of a problematic assignment can be identified
over the AST in a way similar to what is done by escape analysis, possibly
as part of escape analysis. In fact, if escape analysis is causing the
problem, why should its problems be solved in any other part of the
compiler?
Post by Russ Cox
In my earlier message in this thread - the one with a rough
implementation of what I am suggesting - I included a list of all the
variables in the standard tree that appear to need zeroing if we use stack
maps. There are 24 such variables in the entire code base (and at least one
is a false positive, as my message explained). I think it is safe to say
that inserting 24 zeroings across the entire tree will not be too costly,
and I also think it is safe to say that typical code outside the standard
tree will not be significantly different in this regard.
Maybe, assuming this is all correct, see below.
Post by Russ Cox
Will you please add the analysis I am suggesting to this CL?
I copied your plive.c into my client and it crashes my build very quickly.
Did you test any generated code before sending it to me?

# Building C bootstrap tool.
cmd/dist

# Building compilers and Go bootstrap tool for host, linux/amd64.
lib9
libbio
libmach
misc/pprof
cmd/addr2line
cmd/nm
cmd/objdump
cmd/pack
cmd/prof
cmd/cc
cmd/gc
cmd/6l
cmd/6a
cmd/6c
cmd/6g
pkg/runtime
pkg/errors
pkg/sync/atomic
pkg/sync
pkg/io
pkg/unicode
pkg/unicode/utf8
pkg/unicode/utf16
pkg/bytes
pkg/math
pkg/strings
pkg/strconv
pkg/bufio
pkg/sort
pkg/container/heap
pkg/encoding/base64
pkg/syscall
pkg/time
pkg/os
pkg/reflect
pkg/fmt
pkg/encoding
pkg/encoding/json
pkg/flag
pkg/path/filepath
pkg/path
pkg/io/ioutil
pkg/log
pkg/regexp/syntax
pkg/regexp
pkg/go/token
pkg/go/scanner
pkg/go/ast
pkg/go/parser
pkg/os/exec
pkg/os/signal
/usr/local/google/home/cshapiro/go/src/pkg/os/signal/signal.go:88: Notify:
h (type *handler) is ambiguously live
pkg/net/url
pkg/text/template/parse
pkg/text/template
pkg/go/doc
pkg/go/build
cmd/go
/usr/local/google/home/cshapiro/go/src/cmd/go/list.go:153: runList: tmpl
(type *template.Template) is ambiguously live
/usr/local/google/home/cshapiro/go/src/cmd/go/main.go:533: matchPackages:
src (type string) is ambiguously live
/usr/local/google/home/cshapiro/go/src/cmd/go/vcs.go:515:
repoRootForImportDynamic: metaImport2 (type metaImport) is ambiguously live
/usr/local/google/home/cshapiro/go/src/cmd/go/vcs.go:527:
repoRootForImportDynamic: metaImport (type metaImport) is ambiguously live
unexpected fault address 0x0
fatal error: fault
[signal 0xb code=0x80 addr=0x0 pc=0x4641e4]

goroutine 1 [running]:
runtime.throw(0x987e17)
/usr/local/google/home/cshapiro/go/src/pkg/runtime/panic.c:464 +0x69
fp=0x7f1334b7f188
runtime.sigpanic()
/usr/local/google/home/cshapiro/go/src/pkg/runtime/os_linux.c:237 +0xe9
fp=0x7f1334b7f1a0
runtime.memmove(0xc2100e48f0, 0xc21009d160, 0xeaddeaddeaddead0)
/usr/local/google/home/cshapiro/go/src/pkg/runtime/memmove_amd64.s:104
+0xa4 fp=0x7f1334b7f1a8
main.stringList(0x7f1334b7f7a8, 0xc, 0xc, 0x8, 0x5b8a60, ...)
/usr/local/google/home/cshapiro/go/src/cmd/go/main.go:651 +0x209
fp=0x7f1334b7f278
main.(*Package).load(0xc2100d0800, 0xc21007f360, 0xc2100a0000, 0x0, 0x0,
...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:464 +0x1a1b
fp=0x7f1334b7f870
main.loadImport(0xc210096c31, 0x7, 0xc21009f2a0, 0x2d, 0xc21007f360, ...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:262 +0x45b
fp=0x7f1334b7f978
main.(*Package).load(0xc2100cb800, 0xc21007f360, 0xc2100a0580, 0x0, 0x0,
...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:480 +0x2e3f
fp=0x7f1334b7ff70
----- stack segment boundary -----
main.loadImport(0xc210000f39, 0x2, 0xc21009f270, 0x2e, 0xc21007f360, ...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:262 +0x45b
fp=0x7f1334b6a670
main.(*Package).load(0xc2100cb000, 0xc21007f360, 0xc2100a18c0, 0x0, 0x0,
...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:480 +0x2e3f
fp=0x7f1334b6ac68
main.loadImport(0xc210000571, 0x3, 0xc2100b40c0, 0x34, 0xc21007f360, ...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:262 +0x45b
fp=0x7f1334b6ad70
main.(*Package).load(0xc2100cbc00, 0xc21007f360, 0xc2100a1340, 0x0, 0x0,
...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:480 +0x2e3f
fp=0x7f1334b6b368
main.loadImport(0xc2100961b1, 0x9, 0xc210093700, 0x2e, 0xc21007f360, ...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:262 +0x45b
fp=0x7f1334b6b470
main.(*Package).load(0xc2100b7800, 0xc21007f360, 0xc21004edc0, 0x0, 0x0,
...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:480 +0x2e3f
fp=0x7f1334b6ba68
main.loadPackage(0xc210000728, 0x7, 0xc21007f360, 0x0)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:743 +0xacf
fp=0x7f1334b6bc80
main.packagesAndErrors(0xc21007d000, 0x8a, 0x100, 0x24, 0x4844bd, ...)
/usr/local/google/home/cshapiro/go/src/cmd/go/pkg.go:805 +0x33f
fp=0x7f1334b6bd60
main.runClean(0x9858c0, 0xc21000a030, 0x1, 0x1)
/usr/local/google/home/cshapiro/go/src/cmd/go/clean.go:75 +0x3b
fp=0x7f1334b6bdb0
main.main()
/usr/local/google/home/cshapiro/go/src/cmd/go/main.go:161 +0x5b0
fp=0x7f1334b6bf48
runtime.main()
/usr/local/google/home/cshapiro/go/src/pkg/runtime/proc.c:222 +0x11f
fp=0x7f1334b6bfa0
runtime.goexit()
/usr/local/google/home/cshapiro/go/src/pkg/runtime/proc.c:1396
fp=0x7f1334b6bfa8

goroutine 3 [syscall]:
os/signal.loop()
/usr/local/google/home/cshapiro/go/src/pkg/os/signal/signal_unix.go:21 +0x1e
created by os/signal.init·1
/usr/local/google/home/cshapiro/go/src/pkg/os/signal/signal_unix.go:27
+0x31
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Russ Cox
2013-11-22 16:17:24 UTC
Permalink
Post by Carl Shapiro
Post by Russ Cox
This is not relevant to the code in the CL. I'm happy to discuss this in
a separate thread or off list, but I don't want to sidetrack this CL review.
Sorry, this is very relevant to the code in this CL. The changes you are
asking for (including the address taken change I already implemented)
breaks the precision invariant I am trying to establish. The greater goal
is to make the stack scanner type-precise and liveness-precise. What you
are asking for means we are not liveness precise, and that directly
conflicts with what I have set out to do.
Liveness imprecision is very hard on users. It is difficult for users to
reason about. Because of that, users cannot be confident about their space
usage. Moreover, because Go has escape analysis, liveness imprecision
makes space complexity of programs vary depending on whether escape
analysis kicks in or not. You can end up using more space if objects with
heap referents get stack allocated.
Whether or not these problems appear frequent by static analysis really
does not matter to the person with a server that explodes in production
because of a space leak caused by liveness imprecision. The triage of
these bugs and the fix is not straightforward either. Liveness imprecision
has been a problem demonstrated time and again in other systems and by
going down this path we are inviting the same problem.
I am trying to avoid this problem. You need to explain why it is a good
idea to take a different approach and remain exposed to it.
We have been talking about making collection of Go stack frames precise
since January. It was supposed to go into Go 1.2 but was delayed. Nothing
substantial has changed in the garbage collector since January in this
regard. We discussed your alternate approaches in August (in person, off
list). I am not interested in rehashing those discussions. I _am_
interested in making Go better. We are so very close now to making a
significant improvement in the way Go collects garbage. If we can finish
this CL and make the Go stack frame traversals precise, that will be a huge
step forward. If, after that, you want to examine making a change to the
escape analysis great. But let's lock in what we've got now instead of
redesigning and setting things back another few months.
Post by Carl Shapiro
There is nothing in the front end that computes reaching definitions.
Post by Russ Cox
Placing each stack variable in its own slot in the frame avoids any need to
do so. It is certainly possible to add a phase to the front end to build a
control flow graph and use that graph to compute reaching definitions. The
liveness analysis in this CL has already built such a control flow graph,
however, and it is very easy - under 200 lines of code - to use that graph
to get the information we need. I don't understand the objection to doing
so. Even more importantly, using the same control flow analysis for the
stack liveness bitmaps and for the decision about what needs zeroing means
that the two pieces of data are guaranteed to be in sync with each other.
Assuming we want to encode pointers and their potential referents in the
stack map, I do not believe the infrastructure you are referring to is
needed. The condition that gives rise to this situation are values
escaping their scope. This condition is only possible with escape analysis
turned on. The existence of a problematic assignment can be identified
over the AST in a way similar to what is done by escape analysis, possibly
as part of escape analysis. In fact, if escape analysis is causing the
problem, why should its problems be solved in any other part of the
compiler?
The problem is not caused by escape analysis, any more than it is caused by
the presence of pointers in the language. Those are what they are. The goal
here is to write a liveness analysis that works for Go as it exists today,
not Go as you might wish it existed. I have explained how to do that and
sent sample code.
Post by Carl Shapiro
In my earlier message in this thread - the one with a rough
Post by Russ Cox
implementation of what I am suggesting - I included a list of all the
variables in the standard tree that appear to need zeroing if we use stack
maps. There are 24 such variables in the entire code base (and at least one
is a false positive, as my message explained). I think it is safe to say
that inserting 24 zeroings across the entire tree will not be too costly,
and I also think it is safe to say that typical code outside the standard
tree will not be significantly different in this regard.
Maybe, assuming this is all correct, see below.
Post by Russ Cox
Will you please add the analysis I am suggesting to this CL?
I copied your plive.c into my client and it crashes my build very quickly.
Did you test any generated code before sending it to me?
Yes, I did, but not the whole tree. It does appear to fail on some code in
the go command.

I don't expect you to use my plive.c directly. I included it as a backup to
the diff in case the diff was hard to read, and I included the diff as a
backup to the text. What matters is not the code but the algorithm, and the
fact that the algorithm does fit into the liveness framework. When we spoke
Tuesday you argued that the liveness code could not accommodate this
analysis. It can. It was not my intent to write and debug the production
implementation for you. It was my intent only to show how it can be done.

Russ
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Russ Cox
2013-11-22 16:35:50 UTC
Permalink
I would like this CL and the others to be ready to submit on December 1, so
that you do not run into merge conflicts with other Go 1.3 work. We can't
hold up the other work indefinitely.

I propose the following. Do not put the algorithm I have suggested into
this CL. But make it - or some other equally simple and effective solution
that gets us to truly precise collection of Go frames - the next thing you
do. We will not hold up other work on Go 1.3 for that followup CL, but
hopefully it will be limited enough that there should not be any serious
merge conflicts.

Russ
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
rsc-iFWiy5xATs8dnm+
2013-11-20 19:39:52 UTC
Permalink
https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/14430048/diff/220001/src/cmd/gc/plive.c#newcode231
src/cmd/gc/plive.c:231: getvariables(Node *fn)
If you have code that declares a variable x and then the address of x
escapes to the heap, the fn->dcl list contains two variables: x with
class PAUTO|PHEAP, and &x with class PAUTO. Only &x has a place on the
stack. It holds a pointer to x, which is allocated on the heap. The
generated code being fed into this analysis never refers to "x" except
by indirecting through "&x". This function - getvariables - returns both
"x" and "&x" in the list of variables. There's no point in returning
"x", since it does not exist on the stack. The code in
twobitlivepointermap will ignore "x" because it has class PAUTO|PHEAP,
but if you ignore it here instead you will shorten the bit vectors and
therefore the time spent making them converge. (Here I mean the bit
vectors uevar, varkill, livein, liveout, not the stack map bit vectors.)
So the switch below should not mask out PHEAP.

Similarly, there is no reason for liveness analysis on values that do
not contain pointers. Those can be omitted here too, also shortening the
same bit vectors.

switch(ll->n->class) {
case PAUTO:
case PPARAM:
case PPARAMOUT:
if(haspointers(ll->n->type))
arrayadd(result, &ll->n);
}

This will require similar changes in progeffects to avoid looking for
variables that have been omitted.

https://codereview.appspot.com/14430048/
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Russ Cox
2013-11-20 22:19:13 UTC
Permalink
The liveness analysis should identify variables whose address is taken, but
are not moved to the heap, and it should treat such a variable as live at
safe points reachable from the declaration (or equivalently any
initialization or use) of that variable. It should not treat the variable
as live at safe points not reachable from the declaration. This is the
general point I was making two messages earlier in this thread. The purpose
of this mail is to explain how it might be done.

The current code considers every return instruction to be a use of every
variable with an address taken. That goes away.

For any instruction referring to a stack variable n with n->addrtaken,
define avarinit[n] = 1, meaning that n is initialized or used at this
point. Ideally you'd only do this for the initial assignment or declaration
of a zeroed value but it doesn't hurt anything to do all the uses too,
since all the uses must follow the initial assignment or declaration.
avarinit means "this addressed variable has been initialized".

For each basic block, compute bb->avarinit = the OR of all the avarinit of
the instructions in the block. This gives the avarinit values at the end of
the block, considering only the block.

Next, compute the fixed point such that

bb->avarinitany = bb->avarinit OR (the OR of pred->avarinitany for all
pred)
bb->avarinitall = bb->avarinit OR (the AND of pred->avarinitall for all
pred)

avarinitany means "this addressed variable has been initialized on some
path to this point".
avarinitall means "this addressed variable has been initialized on all
paths to this point".

We care about avarinitany to identify the things that must be
conservatively marked live.
We care about avarinitall to identify the things that are guaranteed
initialized.

This is a forward propagation, in contrast to the backward propagation used
for the current equations. For the iteration to converge correctly the
bb->avarinitall must start as all 1s in all but the entry basic block, and
there must be no edges to the entry.

After solving at basic blocks, reconstruct avarinitany and avarinitall at
the instruction level using the same equations. At each safe point, include
the avarinitany set in the stack liveness bitmaps. Also at each safe point,
compute

avarinitany AND NOT avarinitall

If any bits are set, the corresponding variables are ambiguously live (like
y and z in the example two messages ago), and zeroing must be introduced to
make sure they are initialized always, not just sometimes.

If there are a lot of these variables, the best place to insert the zeroing
for n is probably at the first immediate dominator of the safe point for
which addrinitany[n] = 0. This is the latest point in the program where
nothing has initialized the variable.

If there are not many of these variables, we could skip the computation of
the immediate dominator chain and just insert the zeroing at the beginning
of the function, like I did for all the pointer-containing variables in
August.

I made an attempt at this, and if the code is correct it appears there are
very few such variables. Compiling the entire standard library and commands
I get only 24 such variables; the full output is below. The control flow
around calls to deferproc is not quite correct - there is an unnecessary
edge in the graph - and that causes some false positives when defer is
used, like the h variable in os/signal. The true set of such variables is
smaller. But even with the false positives this set of variables is so tiny
that we should be able to just insert zeroing at the beginning of the
function.

I am including the diff against the file I started with below, and I am
attaching my copy of plive.c. I am not suggesting to adopt it wholesale: I
am probably missing some calls to free, and there may be other bugs. But it
stands as a proof that the liveness code can fairly easily identify which
variables need additional zeroing. Setting n->needzero and restoring the
zeroing code (deletion pending in this CL) should suffice to enable fully
precise collection of Go frames.

There are some questions around fat variables. The code in the CL treats
all fat variables as if their addresses were taken. This seems overly
conservative to me. Is it a debugging step that was not rolled back?

Thanks.
Russ

g% go build -a std
# os/signal
pkg/os/signal/signal.go:88: Notify: h (type *handler) is ambiguously live
# go/printer
pkg/go/printer/printer.go:583: (*printer).writeComment: ldir (type string)
is ambiguously live
# cmd/fix
cmd/fix/fix.go:812: renameFixTab: opkg (type string) is ambiguously live
cmd/fix/fix.go:812: renameFixTab: onam (type string) is ambiguously live
cmd/fix/fix.go:842: renameFixTab: t (type rename) is ambiguously live
# cmd/cgo
cmd/cgo/out.go:647: (*Package).writeExports: ctype (type string) is
ambiguously live
cmd/cgo/out.go:647: (*Package).writeExports: s (type string) is ambiguously
live
cmd/cgo/out.go:833: (*Package).writeGccgoExports: cdeclBuf (type
*bytes.Buffer) is ambiguously live
# database/sql
pkg/database/sql/sql.go:891: (*DB).exec: si (type driver.Stmt) is
ambiguously live
pkg/database/sql/sql.go:1194: (*Tx).Exec: si (type driver.Stmt) is
ambiguously live
# encoding/gob
pkg/encoding/gob/type.go:563: newTypeObject: err (type error) is
ambiguously live
# image/png
pkg/image/png/writer.go:413: writeImage: cr (type [5][]uint8) is
ambiguously live
# testing
pkg/testing/example.go:57: runExample: err (type error) is ambiguously live
# net
pkg/net/dial.go:165: (*Dialer).Dial: ras (type addrList) is ambiguously live
pkg/net/lookup.go:90: lookupIPDeadline: r (type res) is ambiguously live
# net/http
pkg/net/http/fs.go:255: serveContent: err (type error) is ambiguously live
pkg/net/http/fs.go:400: serveFile: d (type os.FileInfo) is ambiguously live
pkg/net/http/transport.go:791: (*persistConn).writeLoop: wr (type
writeRequest) is ambiguously live
pkg/net/http/transport.go:879: (*persistConn).roundTrip: err (type error)
is ambiguously live
# net/http/cookiejar
pkg/net/http/cookiejar/jar.go:202: (*Jar).cookies: e (type entry) is
ambiguously live
# cmd/go
cmd/go/list.go:153: runList: tmpl (type *template.Template) is ambiguously
live
cmd/go/main.go:533: matchPackages: src (type string) is ambiguously live
cmd/go/vcs.go:515: repoRootForImportDynamic: metaImport2 (type metaImport)
is ambiguously live
cmd/go/vcs.go:527: repoRootForImportDynamic: metaImport (type metaImport)
is ambiguously live
g%

g% diff -u cmd/gc/plive.c.old cmd/gc/plive.c
--- cmd/gc/plive.c.old 2013-11-20 16:57:15.000000000 -0500
+++ cmd/gc/plive.c 2013-11-20 16:53:52.000000000 -0500
@@ -89,10 +89,9 @@
Bvec **livein;
Bvec **liveout;

- Bvec **addrin;
- Bvec **addrout;
- Bvec **initin;
- Bvec **initout;
+ Bvec **avarinit;
+ Bvec **avarinitany;
+ Bvec **avarinitall;

// An array with a bit vector for each safe point tracking live pointers
// in the arguments and locals area.
@@ -598,7 +597,7 @@
// Computes the upward exposure and kill effects of an instruction on a
set of
// variables. The vars argument is an array of Nodes*s.
static void
-progeffects(Prog *prog, Array *vars, Bvec *uevar, Bvec *varkill)
+progeffects(Prog *prog, Array *vars, Bvec *uevar, Bvec *varkill, Bvec
*avarinit)
{
ProgInfo info;
Adr *from;
@@ -609,6 +608,8 @@

bvresetall(uevar);
bvresetall(varkill);
+ bvresetall(avarinit);
+
proginfo(&info, prog);
if(prog->as == ARET) {
// Return instructions implicitly read all the arguments. For
@@ -621,13 +622,6 @@
case PPARAMOUT:
bvset(uevar, i);
break;
- case PAUTO:
- // Because the lifetime of stack temporaries
- // that have their address taken is undecidable,
- // we conservatively assume their lifetime
- // extends to the return as well.
- if(isfat(node->type) || node->addrtaken)
- bvset(uevar, i);
}
}
return;
@@ -639,7 +633,18 @@
node = *(Node**)arrayget(vars, i);
switch(node->class & ~PHEAP) {
case PPARAM:
+ if(node->addrtaken)
+ bvset(avarinit, i);
bvset(varkill, i);
+ break;
+ case PPARAMOUT:
+ // TODO: Should not be necessary - the code should contain
+ // an explicit initialization of node at the beginning of the
+ // function. Apparently the analysis cannot see that initialization.
+ // That's a bug and we need to understand it.
+ if(node->addrtaken)
+ bvset(avarinit, i);
+ break;
}
}
return;
@@ -654,14 +659,22 @@
pos = arrayindexof(vars, from->node);
if(pos == -1)
goto next;
- if((info.flags & LeftRead) || (info.flags & LeftAddr))
+ if((info.flags & LeftRead) || (info.flags & LeftAddr)) {
+ if(from->node->addrtaken)
+ bvset(avarinit, pos);
bvset(uevar, pos);
- if(info.flags & LeftWrite)
- if(from->node != nil && (!isfat(from->node->type) || prog->as ==
AFATVARDEF))
+ }
+ if(info.flags & LeftWrite) {
+ if(from->node != nil && (!isfat(from->node->type) || prog->as ==
AFATVARDEF)) {
+ if(from->node->addrtaken)
+ bvset(avarinit, pos);
bvset(varkill, pos);
+ }
+ }
}
}
}
+
next:
if(info.flags & (RightRead | RightWrite | RightAddr)) {
to = &prog->to;
@@ -673,11 +686,18 @@
pos = arrayindexof(vars, to->node);
if(pos == -1)
goto next1;
- if((info.flags & RightRead) || (info.flags & RightAddr))
+ if((info.flags & RightRead) || (info.flags & RightAddr)) {
+ if(to->node->addrtaken)
+ bvset(avarinit, pos);
bvset(uevar, pos);
- if(info.flags & RightWrite)
- if(to->node != nil && (!isfat(to->node->type) || prog->as == AFATVARDEF))
+ }
+ if(info.flags & RightWrite) {
+ if(to->node != nil && (!isfat(to->node->type) || prog->as == AFATVARDEF))
{
+ if(to->node->addrtaken)
+ bvset(avarinit, pos);
bvset(varkill, pos);
+ }
+ }
}
}
}
@@ -706,6 +726,9 @@
result->varkill = xmalloc(sizeof(Bvec*) * nblocks);
result->livein = xmalloc(sizeof(Bvec*) * nblocks);
result->liveout = xmalloc(sizeof(Bvec*) * nblocks);
+ result->avarinit = xmalloc(sizeof(Bvec*) * nblocks);
+ result->avarinitany = xmalloc(sizeof(Bvec*) * nblocks);
+ result->avarinitall = xmalloc(sizeof(Bvec*) * nblocks);

nvars = arraylength(vars);
for(i = 0; i < nblocks; i++) {
@@ -713,6 +736,9 @@
result->varkill[i] = bvalloc(nvars);
result->livein[i] = bvalloc(nvars);
result->liveout[i] = bvalloc(nvars);
+ result->avarinit[i] = bvalloc(nvars);
+ result->avarinitany[i] = bvalloc(nvars);
+ result->avarinitall[i] = bvalloc(nvars);
}

result->livepointers = arraynew(0, sizeof(Bvec*));
@@ -763,13 +789,15 @@
}

static void
-printeffects(Prog *p, Bvec *uevar, Bvec *varkill)
+printeffects(Prog *p, Bvec *uevar, Bvec *varkill, Bvec *avarinit)
{
print("effects of %P", p);
print("\nuevar: ");
bvprint(uevar);
print("\nvarkill: ");
bvprint(varkill);
+ print("\navarinit: ");
+ bvprint(avarinit);
print("\n");
}

@@ -779,6 +807,7 @@
BasicBlock *bb;
Bvec *uevar;
Bvec *varkill;
+ Bvec *avarinit;
Prog *prog;
int32 i;
int32 nvars;
@@ -786,20 +815,26 @@
nvars = arraylength(lv->vars);
uevar = bvalloc(nvars);
varkill = bvalloc(nvars);
+ avarinit = bvalloc(nvars);
for(i = 0; i < arraylength(lv->cfg); i++) {
bb = *(BasicBlock**)arrayget(lv->cfg, i);
// Walk the block instructions backward and update the block
// effects with the each prog effects.
for(prog = bb->last; prog != nil; prog = prog->opt) {
- progeffects(prog, lv->vars, uevar, varkill);
- if(Debug) printeffects(prog, uevar, varkill);
+ progeffects(prog, lv->vars, uevar, varkill, avarinit);
+ if(Debug) printeffects(prog, uevar, varkill, avarinit);
bvor(lv->varkill[i], lv->varkill[i], varkill);
bvandnot(lv->uevar[i], lv->uevar[i], varkill);
bvor(lv->uevar[i], lv->uevar[i], uevar);
+
+ bvor(lv->avarinit[i], lv->avarinit[i], avarinit);
+ bvor(lv->avarinitall[i], lv->avarinitall[i], avarinit);
+ bvor(lv->avarinitany[i], lv->avarinitany[i], avarinit);
}
}
free(uevar);
free(varkill);
+ free(avarinit);
}

// Solve the liveness dataflow equations.
@@ -808,8 +843,10 @@
{
BasicBlock *bb;
BasicBlock *succ;
+ BasicBlock *pred;
Bvec *newlivein;
Bvec *newliveout;
+ Bvec *any, *all;
int32 rpo;
int32 i;
int32 j;
@@ -819,6 +856,53 @@
// frees within the loop.
newlivein = bvalloc(arraylength(lv->vars));
newliveout = bvalloc(arraylength(lv->vars));
+ any = bvalloc(arraylength(lv->vars));
+ all = bvalloc(arraylength(lv->vars));
+
+ // Push avarinitall, avarinitany forward.
+ // avarinitall says the addressed var is initialized along all paths
reaching this point.
+ // avarinitany says the addressed var is used along some path reaching
this point.
+ for(i = 0; i < arraylength(lv->cfg); i++) {
+ bb = *(BasicBlock**)arrayget(lv->cfg, i);
+ rpo = bb->rpo;
+ if(i == 0)
+ bvcopy(lv->avarinitall[rpo], lv->avarinit[rpo]);
+ else {
+ bvresetall(lv->avarinitall[rpo]);
+ bvnot(lv->avarinitall[rpo]);
+ }
+ }
+
+ change = 1;
+ while(change != 0) {
+ change = 0;
+ for(i = 0; i < arraylength(lv->cfg); i++) {
+ bb = *(BasicBlock**)arrayget(lv->cfg, i);
+ rpo = bb->rpo;
+ bvresetall(any);
+ bvresetall(all);
+ for(j = 0; j < arraylength(bb->pred); j++) {
+ pred = *(BasicBlock**)arrayget(bb->pred, j);
+ if(j == 0) {
+ bvcopy(any, lv->avarinitany[pred->rpo]);
+ bvcopy(all, lv->avarinitall[pred->rpo]);
+ } else {
+ bvor(any, any, lv->avarinitany[pred->rpo]);
+ bvand(all, all, lv->avarinitall[pred->rpo]);
+ }
+ }
+ bvor(any, any, lv->avarinit[rpo]);
+ bvor(all, all, lv->avarinit[rpo]);
+ if(bvcmp(any, lv->avarinitany[rpo])) {
+ change = 1;
+ bvcopy(lv->avarinitany[rpo], any);
+ }
+ if(bvcmp(all, lv->avarinitall[rpo])) {
+ change = 1;
+ bvcopy(lv->avarinitall[rpo], all);
+ }
+ }
+ }

// Iterate through the blocks in reverse round-robin fashion. A work
// queue might be slightly faster. As is, the number of iterations is
@@ -849,6 +933,8 @@

free(newlivein);
free(newliveout);
+ free(any);
+ free(all);
}


@@ -921,6 +1007,9 @@
printvars("\tvarkill", lv->varkill[bb->rpo], lv->vars);
printvars("\tlivein", lv->livein[bb->rpo], lv->vars);
printvars("\tliveout", lv->liveout[bb->rpo], lv->vars);
+ printvars("\tavarinit", lv->avarinit[bb->rpo], lv->vars);
+ printvars("\tavarinitall", lv->avarinitall[bb->rpo], lv->vars);
+ printvars("\tavarinitany", lv->avarinitany[bb->rpo], lv->vars);

print("\tprog:\n");
for(prog = bb->first;; prog = prog->link) {
@@ -1322,47 +1411,92 @@
static void
livenessepilogue(Liveness *lv)
{
- BasicBlock *bb;
+ BasicBlock *bb, *pred;
Bvec *livein;
Bvec *liveout;
Bvec *uevar;
Bvec *varkill;
Bvec *args;
Bvec *locals;
+ Bvec *avarinit;
+ Bvec *any, *all;
Prog *p;
- int32 i;
+ int32 i, j;
int32 nvars;
int32 pos;
+ Node *n;

nvars = arraylength(lv->vars);
livein = bvalloc(nvars);
liveout = bvalloc(nvars);
uevar = bvalloc(nvars);
varkill = bvalloc(nvars);
+ avarinit = bvalloc(nvars);
+ any = bvalloc(nvars);
+ all = bvalloc(nvars);

for(i = 0; i < arraylength(lv->cfg); i++) {
bb = *(BasicBlock**)arrayget(lv->cfg, i);
- bvcopy(livein, lv->liveout[bb->rpo]);
+
+ bvresetall(any);
+ bvresetall(all);
+ for(j = 0; j < arraylength(bb->pred); j++) {
+ pred = *(BasicBlock**)arrayget(bb->pred, j);
+ if(j == 0) {
+ bvcopy(any, lv->avarinitany[pred->rpo]);
+ bvcopy(all, lv->avarinitall[pred->rpo]);
+ } else {
+ bvor(any, any, lv->avarinitany[pred->rpo]);
+ bvand(all, all, lv->avarinitall[pred->rpo]);
+ }
+ }
+
// Walk forward through the basic block instructions and
// allocate and empty map for those instructions that need them
- for(p = bb->last; p != nil; p = p->opt) {
- if(!issafepoint(p))
- continue;
+ for(p = bb->first;; p = p->link) {
+ progeffects(p, lv->vars, uevar, varkill, avarinit);
+ bvor(any, any, avarinit);
+ bvor(all, all, avarinit);
+
+ if(issafepoint(p)) {
+ bvresetall(livein);
+ bvandnot(liveout, any, all);
+ if(bvcmp(livein, liveout) != 0) {
+ for(pos = 0; pos < liveout->n; pos++)
+ if(bvget(liveout, pos)) {
+ n = *(Node**)arrayget(lv->vars, pos);
+ if(!n->diag) {
+ warnl(p->lineno, "%N: %lN is ambiguously live", curfn->nname, n);
+ n->diag = 1;
+ }
+ bvset(all, pos);
+ }
+ }

- // Allocate a bit vector for each class and facet of
- // value we are tracking.
+ // Allocate a bit vector for each class and facet of
+ // value we are tracking.
+
+ // Live stuff first.
+ args = bvalloc(argswords() * BitsPerPointer);
+ arrayadd(lv->argslivepointers, &args);
+ locals = bvalloc(localswords() * BitsPerPointer);
+ arrayadd(lv->livepointers, &locals);
+
+ if(Debug) {
+ print("%P\n", p);
+ printvars("avarinitany", any, lv->vars);
+ }
+ twobitlivepointermap(lv, any, lv->vars, args, locals);
+
+ // Dead stuff second.
+ args = bvalloc(argswords() * BitsPerPointer);
+ arrayadd(lv->argsdeadvalues, &args);
+ locals = bvalloc(localswords() * BitsPerPointer);
+ arrayadd(lv->deadvalues, &locals);
+ }

- // Live stuff first.
- args = bvalloc(argswords() * BitsPerPointer);
- arrayadd(lv->argslivepointers, &args);
- locals = bvalloc(localswords() * BitsPerPointer);
- arrayadd(lv->livepointers, &locals);
-
- // Dead stuff second.
- args = bvalloc(argswords() * BitsPerPointer);
- arrayadd(lv->argsdeadvalues, &args);
- locals = bvalloc(localswords() * BitsPerPointer);
- arrayadd(lv->deadvalues, &locals);
+ if(p == bb->last)
+ break;
}

// walk backward, emit pcdata and populate the maps
@@ -1372,9 +1506,10 @@
// at no point should pos ever be less than zero.
fatal("livenessepilogue");

+ bvcopy(livein, lv->liveout[bb->rpo]);
for(p = bb->last; p != nil; p = p->opt) {
// Propagate liveness information
- progeffects(p, lv->vars, uevar, varkill);
+ progeffects(p, lv->vars, uevar, varkill, avarinit);
bvcopy(liveout, livein);
bvandnot(livein, liveout, varkill);
bvor(livein, livein, uevar);
@@ -1409,6 +1544,9 @@
}
}

+ //print("%P\n", p);
+ //printvars("liveout", liveout, lv->vars);
+
// Record live pointers.
args = *(Bvec**)arrayget(lv->argslivepointers, pos);
locals = *(Bvec**)arrayget(lv->livepointers, pos);
@@ -1428,6 +1566,8 @@
free(liveout);
free(uevar);
free(varkill);
+ free(avarinit);
+ free(any);
}

// Dumps an array of bitmaps to a symbol as a sequence of uint32 values.
The
g%
--
---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit https://groups.google.com/groups/opt_out.
Loading...