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.