diff options
Diffstat (limited to 'src/cmd/gc/plive.c')
| -rw-r--r-- | src/cmd/gc/plive.c | 1985 |
1 files changed, 1985 insertions, 0 deletions
diff --git a/src/cmd/gc/plive.c b/src/cmd/gc/plive.c new file mode 100644 index 000000000..eb8901733 --- /dev/null +++ b/src/cmd/gc/plive.c @@ -0,0 +1,1985 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Garbage collector liveness bitmap generation. + +// The command line flag -live causes this code to print debug information. +// The levels are: +// +// -live (aka -live=1): print liveness lists as code warnings at safe points +// -live=2: print an assembly listing with liveness annotations +// -live=3: print information during each computation phase (much chattier) +// +// Each level includes the earlier output as well. + +#include <u.h> +#include <libc.h> +#include "gg.h" +#include "opt.h" +#include "../../pkg/runtime/funcdata.h" + +enum { BitsPerPointer = 2 }; + +enum { + UNVISITED = 0, + VISITED = 1, +}; + +// An ordinary basic block. +// +// Instructions are threaded together in a doubly-linked list. To iterate in +// program order follow the link pointer from the first node and stop after the +// last node has been visited +// +// for(p = bb->first;; p = p->link) { +// ... +// if(p == bb->last) +// break; +// } +// +// To iterate in reverse program order by following the opt pointer from the +// last node +// +// for(p = bb->last; p != nil; p = p->opt) { +// ... +// } +typedef struct BasicBlock BasicBlock; +struct BasicBlock { + // An array of preceding blocks. If the length of this array is 0 the + // block is probably the start block of the CFG. + Array *pred; + + // An array out succeeding blocks. If the length of this array is zero, + // the block probably ends in a return instruction. + Array *succ; + + // First instruction in the block. When part of a fully initialized + // control flow graph, the opt member will be nil. + Prog *first; + + // Last instruction in the basic block. + Prog *last; + + // The reverse post order number. This value is initialized to -1 and + // will be replaced by a non-negative value when the CFG is constructed. + // After CFG construction, if rpo is -1 this block is unreachable. + int rpo; + + // State to denote whether the block has been visited during a + // traversal. + int mark; + + // For use during livenessepilogue. + int lastbitmapindex; +}; + +// A collection of global state used by liveness analysis. +typedef struct Liveness Liveness; +struct Liveness { + // A pointer to the node corresponding to the function being analyzed. + Node *fn; + + // A linked list of instructions for this function. + Prog *ptxt; + + // A list of arguments and local variables in this function. + Array *vars; + + // A list of basic blocks that are overlayed on the instruction list. + // The blocks are roughly in the same order as the instructions + // in the function (first block has TEXT instruction, and so on). + Array *cfg; + + // Summary sets of block effects. + // The Bvec** is indexed by bb->rpo to yield a single Bvec*. + // That bit vector is indexed by variable number (same as lv->vars). + // + // Computed during livenessprologue using only the content of + // individual blocks: + // + // uevar: upward exposed variables (used before set in block) + // varkill: killed variables (set in block) + // avarinit: addrtaken variables set or used (proof of initialization) + // + // Computed during livenesssolve using control flow information: + // + // livein: variables live at block entry + // liveout: variables live at block exit + // avarinitany: addrtaken variables possibly initialized at block exit + // (initialized in block or at exit from any predecessor block) + // avarinitall: addrtaken variables certainly initialized at block exit + // (initialized in block or at exit from all predecessor blocks) + Bvec **uevar; + Bvec **varkill; + Bvec **livein; + Bvec **liveout; + 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, indexed by bb->rpo. + Array *argslivepointers; + Array *livepointers; +}; + +static void* +xmalloc(uintptr size) +{ + void *result; + + result = malloc(size); + if(result == nil) + fatal("malloc failed"); + return result; +} + +// Constructs a new basic block containing a single instruction. +static BasicBlock* +newblock(Prog *prog) +{ + BasicBlock *result; + + if(prog == nil) + fatal("newblock: prog cannot be nil"); + result = xmalloc(sizeof(*result)); + result->rpo = -1; + result->mark = UNVISITED; + result->first = prog; + result->last = prog; + result->pred = arraynew(2, sizeof(BasicBlock*)); + result->succ = arraynew(2, sizeof(BasicBlock*)); + return result; +} + +// Frees a basic block and all of its leaf data structures. +static void +freeblock(BasicBlock *bb) +{ + if(bb == nil) + fatal("freeblock: cannot free nil"); + arrayfree(bb->pred); + arrayfree(bb->succ); + free(bb); +} + +// Adds an edge between two basic blocks by making from a predecessor of to and +// to a successor of from. +static void +addedge(BasicBlock *from, BasicBlock *to) +{ + if(from == nil) + fatal("addedge: from is nil"); + if(to == nil) + fatal("addedge: to is nil"); + arrayadd(from->succ, &to); + arrayadd(to->pred, &from); +} + +// Inserts prev before curr in the instruction +// stream. Any control flow, such as branches or fall throughs, that target the +// existing instruction are adjusted to target the new instruction. +static void +splicebefore(Liveness *lv, BasicBlock *bb, Prog *prev, Prog *curr) +{ + Prog *next, tmp; + + USED(lv); + + // There may be other instructions pointing at curr, + // and we want them to now point at prev. Instead of + // trying to find all such instructions, swap the contents + // so that the problem becomes inserting next after curr. + // The "opt" field is the backward link in the linked list. + + // Overwrite curr's data with prev, but keep the list links. + tmp = *curr; + *curr = *prev; + curr->opt = tmp.opt; + curr->link = tmp.link; + + // Overwrite prev (now next) with curr's old data. + next = prev; + *next = tmp; + next->opt = nil; + next->link = nil; + + // Now insert next after curr. + next->link = curr->link; + next->opt = curr; + curr->link = next; + if(next->link && next->link->opt == curr) + next->link->opt = next; + + if(bb->last == curr) + bb->last = next; +} + +// A pretty printer for basic blocks. +static void +printblock(BasicBlock *bb) +{ + BasicBlock *pred; + BasicBlock *succ; + Prog *prog; + int i; + + print("basic block %d\n", bb->rpo); + print("\tpred:"); + for(i = 0; i < arraylength(bb->pred); i++) { + pred = *(BasicBlock**)arrayget(bb->pred, i); + print(" %d", pred->rpo); + } + print("\n"); + print("\tsucc:"); + for(i = 0; i < arraylength(bb->succ); i++) { + succ = *(BasicBlock**)arrayget(bb->succ, i); + print(" %d", succ->rpo); + } + print("\n"); + print("\tprog:\n"); + for(prog = bb->first;; prog=prog->link) { + print("\t\t%P\n", prog); + if(prog == bb->last) + break; + } +} + + +// Iterates over a basic block applying a callback to each instruction. There +// are two criteria for termination. If the end of basic block is reached a +// value of zero is returned. If the callback returns a non-zero value, the +// iteration is stopped and the value of the callback is returned. +static int +blockany(BasicBlock *bb, int (*callback)(Prog*)) +{ + Prog *p; + int result; + + for(p = bb->last; p != nil; p = p->opt) { + result = (*callback)(p); + if(result != 0) + return result; + } + return 0; +} + +// Collects and returns and array of Node*s for functions arguments and local +// variables. +static Array* +getvariables(Node *fn) +{ + Array *result; + NodeList *ll; + + result = arraynew(0, sizeof(Node*)); + for(ll = fn->dcl; ll != nil; ll = ll->next) { + if(ll->n->op == ONAME) { + // In order for GODEBUG=gcdead=1 to work, each bitmap needs + // to contain information about all variables covered by the bitmap. + // For local variables, the bitmap only covers the stkptrsize + // bytes in the frame where variables containing pointers live. + // For arguments and results, the bitmap covers all variables, + // so we must include all the variables, even the ones without + // pointers. + switch(ll->n->class) { + case PAUTO: + if(haspointers(ll->n->type)) + arrayadd(result, &ll->n); + break; + case PPARAM: + case PPARAMOUT: + arrayadd(result, &ll->n); + break; + } + } + } + return result; +} + +// A pretty printer for control flow graphs. Takes an array of BasicBlock*s. +static void +printcfg(Array *cfg) +{ + BasicBlock *bb; + int32 i; + + for(i = 0; i < arraylength(cfg); i++) { + bb = *(BasicBlock**)arrayget(cfg, i); + printblock(bb); + } +} + +// Assigns a reverse post order number to each connected basic block using the +// standard algorithm. Unconnected blocks will not be affected. +static void +reversepostorder(BasicBlock *root, int32 *rpo) +{ + BasicBlock *bb; + int i; + + root->mark = VISITED; + for(i = 0; i < arraylength(root->succ); i++) { + bb = *(BasicBlock**)arrayget(root->succ, i); + if(bb->mark == UNVISITED) + reversepostorder(bb, rpo); + } + *rpo -= 1; + root->rpo = *rpo; +} + +// Comparison predicate used for sorting basic blocks by their rpo in ascending +// order. +static int +blockrpocmp(const void *p1, const void *p2) +{ + BasicBlock *bb1; + BasicBlock *bb2; + + bb1 = *(BasicBlock**)p1; + bb2 = *(BasicBlock**)p2; + if(bb1->rpo < bb2->rpo) + return -1; + if(bb1->rpo > bb2->rpo) + return 1; + return 0; +} + +// A pattern matcher for call instructions. Returns true when the instruction +// is a call to a specific package qualified function name. +static int +iscall(Prog *prog, LSym *name) +{ + if(prog == nil) + fatal("iscall: prog is nil"); + if(name == nil) + fatal("iscall: function name is nil"); + if(prog->as != ACALL) + return 0; + return name == prog->to.sym; +} + +// Returns true for instructions that call a runtime function implementing a +// select communication clause. +static int +isselectcommcasecall(Prog *prog) +{ + static LSym* names[5]; + int32 i; + + if(names[0] == nil) { + names[0] = linksym(pkglookup("selectsend", runtimepkg)); + names[1] = linksym(pkglookup("selectrecv", runtimepkg)); + names[2] = linksym(pkglookup("selectrecv2", runtimepkg)); + names[3] = linksym(pkglookup("selectdefault", runtimepkg)); + } + for(i = 0; names[i] != nil; i++) + if(iscall(prog, names[i])) + return 1; + return 0; +} + +// Returns true for call instructions that target runtime·newselect. +static int +isnewselect(Prog *prog) +{ + static LSym *sym; + + if(sym == nil) + sym = linksym(pkglookup("newselect", runtimepkg)); + return iscall(prog, sym); +} + +// Returns true for call instructions that target runtime·selectgo. +static int +isselectgocall(Prog *prog) +{ + static LSym *sym; + + if(sym == nil) + sym = linksym(pkglookup("selectgo", runtimepkg)); + return iscall(prog, sym); +} + +static int +isdeferreturn(Prog *prog) +{ + static LSym *sym; + + if(sym == nil) + sym = linksym(pkglookup("deferreturn", runtimepkg)); + return iscall(prog, sym); +} + +// Walk backwards from a runtime·selectgo call up to its immediately dominating +// runtime·newselect call. Any successor nodes of communication clause nodes +// are implicit successors of the runtime·selectgo call node. The goal of this +// analysis is to add these missing edges to complete the control flow graph. +static void +addselectgosucc(BasicBlock *selectgo) +{ + BasicBlock *pred; + BasicBlock *succ; + + pred = selectgo; + for(;;) { + if(arraylength(pred->pred) == 0) + fatal("selectgo does not have a newselect"); + pred = *(BasicBlock**)arrayget(pred->pred, 0); + if(blockany(pred, isselectcommcasecall)) { + // A select comm case block should have exactly one + // successor. + if(arraylength(pred->succ) != 1) + fatal("select comm case has too many successors"); + succ = *(BasicBlock**)arrayget(pred->succ, 0); + // Its successor should have exactly two successors. + // The drop through should flow to the selectgo block + // and the branch should lead to the select case + // statements block. + if(arraylength(succ->succ) != 2) + fatal("select comm case successor has too many successors"); + // Add the block as a successor of the selectgo block. + addedge(selectgo, succ); + } + if(blockany(pred, isnewselect)) { + // Reached the matching newselect. + break; + } + } +} + +// The entry point for the missing selectgo control flow algorithm. Takes an +// array of BasicBlock*s containing selectgo calls. +static void +fixselectgo(Array *selectgo) +{ + BasicBlock *bb; + int32 i; + + for(i = 0; i < arraylength(selectgo); i++) { + bb = *(BasicBlock**)arrayget(selectgo, i); + addselectgosucc(bb); + } +} + +// Constructs a control flow graph from a sequence of instructions. This +// procedure is complicated by various sources of implicit control flow that are +// not accounted for using the standard cfg construction algorithm. Returns an +// array of BasicBlock*s in control flow graph form (basic blocks ordered by +// their RPO number). +static Array* +newcfg(Prog *firstp) +{ + Prog *p; + Prog *prev; + BasicBlock *bb; + Array *cfg; + Array *selectgo; + int32 i; + int32 rpo; + + // Reset the opt field of each prog to nil. In the first and second + // passes, instructions that are labels temporarily use the opt field to + // point to their basic block. In the third pass, the opt field reset + // to point to the predecessor of an instruction in its basic block. + for(p = firstp; p != P; p = p->link) + p->opt = nil; + + // Allocate an array to remember where we have seen selectgo calls. + // These blocks will be revisited to add successor control flow edges. + selectgo = arraynew(0, sizeof(BasicBlock*)); + + // Loop through all instructions identifying branch targets + // and fall-throughs and allocate basic blocks. + cfg = arraynew(0, sizeof(BasicBlock*)); + bb = newblock(firstp); + arrayadd(cfg, &bb); + for(p = firstp; p != P; p = p->link) { + if(p->to.type == D_BRANCH) { + if(p->to.u.branch == nil) + fatal("prog branch to nil"); + if(p->to.u.branch->opt == nil) { + p->to.u.branch->opt = newblock(p->to.u.branch); + arrayadd(cfg, &p->to.u.branch->opt); + } + if(p->as != AJMP && p->link != nil && p->link->opt == nil) { + p->link->opt = newblock(p->link); + arrayadd(cfg, &p->link->opt); + } + } else if(isselectcommcasecall(p) || isselectgocall(p)) { + // Accommodate implicit selectgo control flow. + if(p->link->opt == nil) { + p->link->opt = newblock(p->link); + arrayadd(cfg, &p->link->opt); + } + } + } + + // Loop through all basic blocks maximally growing the list of + // contained instructions until a label is reached. Add edges + // for branches and fall-through instructions. + for(i = 0; i < arraylength(cfg); i++) { + bb = *(BasicBlock**)arrayget(cfg, i); + for(p = bb->last; p != nil; p = p->link) { + if(p->opt != nil && p != bb->last) + break; + bb->last = p; + + // Stop before an unreachable RET, to avoid creating + // unreachable control flow nodes. + if(p->link != nil && p->link->as == ARET && p->link->mode == 1) + break; + + // Collect basic blocks with selectgo calls. + if(isselectgocall(p)) + arrayadd(selectgo, &bb); + } + if(bb->last->to.type == D_BRANCH) + addedge(bb, bb->last->to.u.branch->opt); + if(bb->last->link != nil) { + // Add a fall-through when the instruction is + // not an unconditional control transfer. + switch(bb->last->as) { + case AJMP: + case ARET: + case AUNDEF: + break; + default: + addedge(bb, bb->last->link->opt); + } + } + } + + // Add back links so the instructions in a basic block can be traversed + // backward. This is the final state of the instruction opt field. + for(i = 0; i < arraylength(cfg); i++) { + bb = *(BasicBlock**)arrayget(cfg, i); + p = bb->first; + prev = nil; + for(;;) { + p->opt = prev; + if(p == bb->last) + break; + prev = p; + p = p->link; + } + } + + // Add missing successor edges to the selectgo blocks. + if(arraylength(selectgo)) + fixselectgo(selectgo); + arrayfree(selectgo); + + // Find a depth-first order and assign a depth-first number to + // all basic blocks. + for(i = 0; i < arraylength(cfg); i++) { + bb = *(BasicBlock**)arrayget(cfg, i); + bb->mark = UNVISITED; + } + bb = *(BasicBlock**)arrayget(cfg, 0); + rpo = arraylength(cfg); + reversepostorder(bb, &rpo); + + // Sort the basic blocks by their depth first number. The + // array is now a depth-first spanning tree with the first + // node being the root. + arraysort(cfg, blockrpocmp); + bb = *(BasicBlock**)arrayget(cfg, 0); + + // Unreachable control flow nodes are indicated by a -1 in the rpo + // field. If we see these nodes something must have gone wrong in an + // upstream compilation phase. + if(bb->rpo == -1) { + print("newcfg: unreachable basic block for %P\n", bb->last); + printcfg(cfg); + fatal("newcfg: invalid control flow graph"); + } + + return cfg; +} + +// Frees a control flow graph (an array of BasicBlock*s) and all of its leaf +// data structures. +static void +freecfg(Array *cfg) +{ + BasicBlock *bb; + BasicBlock *bb0; + Prog *p; + int32 i; + int32 len; + + len = arraylength(cfg); + if(len > 0) { + bb0 = *(BasicBlock**)arrayget(cfg, 0); + for(p = bb0->first; p != P; p = p->link) { + p->opt = nil; + } + for(i = 0; i < len; i++) { + bb = *(BasicBlock**)arrayget(cfg, i); + freeblock(bb); + } + } + arrayfree(cfg); +} + +// Returns true if the node names a variable that is otherwise uninteresting to +// the liveness computation. +static int +isfunny(Node *node) +{ + char *names[] = { ".fp", ".args", nil }; + int i; + + if(node->sym != nil && node->sym->name != nil) + for(i = 0; names[i] != nil; i++) + if(strcmp(node->sym->name, names[i]) == 0) + return 1; + return 0; +} + +// Computes the effects of an instruction on a set of +// variables. The vars argument is an array of Node*s. +// +// The output vectors give bits for variables: +// uevar - used by this instruction +// varkill - killed by this instruction +// for variables without address taken, means variable was set +// for variables with address taken, means variable was marked dead +// avarinit - initialized or referred to by this instruction, +// only for variables with address taken but not escaping to heap +// +// The avarinit output serves as a signal that the data has been +// initialized, because any use of a variable must come after its +// initialization. +static void +progeffects(Prog *prog, Array *vars, Bvec *uevar, Bvec *varkill, Bvec *avarinit) +{ + ProgInfo info; + Adr *from; + Adr *to; + Node *node; + int32 i; + int32 pos; + + bvresetall(uevar); + bvresetall(varkill); + bvresetall(avarinit); + + proginfo(&info, prog); + if(prog->as == ARET) { + // Return instructions implicitly read all the arguments. For + // the sake of correctness, out arguments must be read. For the + // sake of backtrace quality, we read in arguments as well. + // + // A return instruction with a p->to is a tail return, which brings + // the stack pointer back up (if it ever went down) and then jumps + // to a new function entirely. That form of instruction must read + // all the parameters for correctness, and similarly it must not + // read the out arguments - they won't be set until the new + // function runs. + for(i = 0; i < arraylength(vars); i++) { + node = *(Node**)arrayget(vars, i); + switch(node->class & ~PHEAP) { + case PPARAM: + bvset(uevar, i); + break; + case PPARAMOUT: + // If the result had its address taken, it is being tracked + // by the avarinit code, which does not use uevar. + // If we added it to uevar too, we'd not see any kill + // and decide that the varible was live entry, which it is not. + // So only use uevar in the non-addrtaken case. + // The p->to.type == D_NONE limits the bvset to + // non-tail-call return instructions; see note above + // the for loop for details. + if(!node->addrtaken && prog->to.type == D_NONE) + bvset(uevar, i); + break; + } + } + return; + } + if(prog->as == ATEXT) { + // A text instruction marks the entry point to a function and + // the definition point of all in arguments. + for(i = 0; i < arraylength(vars); i++) { + node = *(Node**)arrayget(vars, i); + switch(node->class & ~PHEAP) { + case PPARAM: + if(node->addrtaken) + bvset(avarinit, i); + bvset(varkill, i); + break; + } + } + return; + } + if(info.flags & (LeftRead | LeftWrite | LeftAddr)) { + from = &prog->from; + if (from->node != nil && from->sym != nil) { + switch(from->node->class & ~PHEAP) { + case PAUTO: + case PPARAM: + case PPARAMOUT: + pos = arrayindexof(vars, from->node); + if(pos == -1) + goto Next; + if(from->node->addrtaken) { + bvset(avarinit, pos); + } else { + if(info.flags & (LeftRead | LeftAddr)) + bvset(uevar, pos); + if(info.flags & LeftWrite) + if(from->node != nil && !isfat(from->node->type)) + bvset(varkill, pos); + } + } + } + } +Next: + if(info.flags & (RightRead | RightWrite | RightAddr)) { + to = &prog->to; + if (to->node != nil && to->sym != nil) { + switch(to->node->class & ~PHEAP) { + case PAUTO: + case PPARAM: + case PPARAMOUT: + pos = arrayindexof(vars, to->node); + if(pos == -1) + goto Next1; + if(to->node->addrtaken) { + if(prog->as != AVARKILL) + bvset(avarinit, pos); + if(prog->as == AVARDEF || prog->as == AVARKILL) + bvset(varkill, pos); + } else { + // RightRead is a read, obviously. + // RightAddr by itself is also implicitly a read. + // + // RightAddr|RightWrite means that the address is being taken + // but only so that the instruction can write to the value. + // It is not a read. It is equivalent to RightWrite except that + // having the RightAddr bit set keeps the registerizer from + // trying to substitute a register for the memory location. + if((info.flags & RightRead) || (info.flags & (RightAddr|RightWrite)) == RightAddr) + bvset(uevar, pos); + if(info.flags & RightWrite) + if(to->node != nil && (!isfat(to->node->type) || prog->as == AVARDEF)) + bvset(varkill, pos); + } + } + } + } +Next1:; +} + +// Constructs a new liveness structure used to hold the global state of the +// liveness computation. The cfg argument is an array of BasicBlock*s and the +// vars argument is an array of Node*s. +static Liveness* +newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars) +{ + Liveness *result; + int32 i; + int32 nblocks; + int32 nvars; + + result = xmalloc(sizeof(*result)); + result->fn = fn; + result->ptxt = ptxt; + result->cfg = cfg; + result->vars = vars; + + nblocks = arraylength(cfg); + result->uevar = xmalloc(sizeof(Bvec*) * nblocks); + 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++) { + result->uevar[i] = bvalloc(nvars); + 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*)); + result->argslivepointers = arraynew(0, sizeof(Bvec*)); + return result; +} + +// Frees the liveness structure and all of its leaf data structures. +static void +freeliveness(Liveness *lv) +{ + int32 i; + + if(lv == nil) + fatal("freeliveness: cannot free nil"); + + for(i = 0; i < arraylength(lv->livepointers); i++) + free(*(Bvec**)arrayget(lv->livepointers, i)); + arrayfree(lv->livepointers); + + for(i = 0; i < arraylength(lv->argslivepointers); i++) + free(*(Bvec**)arrayget(lv->argslivepointers, i)); + arrayfree(lv->argslivepointers); + + for(i = 0; i < arraylength(lv->cfg); i++) { + free(lv->uevar[i]); + free(lv->varkill[i]); + free(lv->livein[i]); + free(lv->liveout[i]); + free(lv->avarinit[i]); + free(lv->avarinitany[i]); + free(lv->avarinitall[i]); + } + + free(lv->uevar); + free(lv->varkill); + free(lv->livein); + free(lv->liveout); + free(lv->avarinit); + free(lv->avarinitany); + free(lv->avarinitall); + + free(lv); +} + +static void +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"); +} + +// Pretty print a variable node. Uses Pascal like conventions for pointers and +// addresses to avoid confusing the C like conventions used in the node variable +// names. +static void +printnode(Node *node) +{ + char *p; + char *a; + + p = haspointers(node->type) ? "^" : ""; + a = node->addrtaken ? "@" : ""; + print(" %N%s%s", node, p, a); +} + +// Pretty print a list of variables. The vars argument is an array of Node*s. +static void +printvars(char *name, Bvec *bv, Array *vars) +{ + int32 i; + + print("%s:", name); + for(i = 0; i < arraylength(vars); i++) + if(bvget(bv, i)) + printnode(*(Node**)arrayget(vars, i)); + print("\n"); +} + +// Prints a basic block annotated with the information computed by liveness +// analysis. +static void +livenessprintblock(Liveness *lv, BasicBlock *bb) +{ + BasicBlock *pred; + BasicBlock *succ; + Prog *prog; + Bvec *live; + int i; + int32 pos; + + print("basic block %d\n", bb->rpo); + + print("\tpred:"); + for(i = 0; i < arraylength(bb->pred); i++) { + pred = *(BasicBlock**)arrayget(bb->pred, i); + print(" %d", pred->rpo); + } + print("\n"); + + print("\tsucc:"); + for(i = 0; i < arraylength(bb->succ); i++) { + succ = *(BasicBlock**)arrayget(bb->succ, i); + print(" %d", succ->rpo); + } + print("\n"); + + printvars("\tuevar", lv->uevar[bb->rpo], lv->vars); + 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("\tavarinitany", lv->avarinitany[bb->rpo], lv->vars); + printvars("\tavarinitall", lv->avarinitall[bb->rpo], lv->vars); + + print("\tprog:\n"); + for(prog = bb->first;; prog = prog->link) { + print("\t\t%P", prog); + if(prog->as == APCDATA && prog->from.offset == PCDATA_StackMapIndex) { + pos = prog->to.offset; + live = *(Bvec**)arrayget(lv->livepointers, pos); + print(" "); + bvprint(live); + } + print("\n"); + if(prog == bb->last) + break; + } +} + +// Prints a control flow graph annotated with any information computed by +// liveness analysis. +static void +livenessprintcfg(Liveness *lv) +{ + BasicBlock *bb; + int32 i; + + for(i = 0; i < arraylength(lv->cfg); i++) { + bb = *(BasicBlock**)arrayget(lv->cfg, i); + livenessprintblock(lv, bb); + } +} + +static void +checkauto(Node *fn, Prog *p, Node *n) +{ + NodeList *l; + + for(l = fn->dcl; l != nil; l = l->next) + if(l->n->op == ONAME && l->n->class == PAUTO && l->n == n) + return; + + print("checkauto %N: %N (%p; class=%d) not found in %P\n", curfn, n, n, n->class, p); + for(l = fn->dcl; l != nil; l = l->next) + print("\t%N (%p; class=%d)\n", l->n, l->n, l->n->class); + yyerror("checkauto: invariant lost"); +} + +static void +checkparam(Node *fn, Prog *p, Node *n) +{ + NodeList *l; + Node *a; + int class; + + if(isfunny(n)) + return; + for(l = fn->dcl; l != nil; l = l->next) { + a = l->n; + class = a->class & ~PHEAP; + if(a->op == ONAME && (class == PPARAM || class == PPARAMOUT) && a == n) + return; + } + + print("checkparam %N: %N (%p; class=%d) not found in %P\n", curfn, n, n, n->class, p); + for(l = fn->dcl; l != nil; l = l->next) + print("\t%N (%p; class=%d)\n", l->n, l->n, l->n->class); + yyerror("checkparam: invariant lost"); +} + +static void +checkprog(Node *fn, Prog *p) +{ + if(p->from.type == D_AUTO) + checkauto(fn, p, p->from.node); + if(p->from.type == D_PARAM) + checkparam(fn, p, p->from.node); + if(p->to.type == D_AUTO) + checkauto(fn, p, p->to.node); + if(p->to.type == D_PARAM) + checkparam(fn, p, p->to.node); +} + +// Check instruction invariants. We assume that the nodes corresponding to the +// sources and destinations of memory operations will be declared in the +// function. This is not strictly true, as is the case for the so-called funny +// nodes and there are special cases to skip over that stuff. The analysis will +// fail if this invariant blindly changes. +static void +checkptxt(Node *fn, Prog *firstp) +{ + Prog *p; + + for(p = firstp; p != P; p = p->link) { + if(0) + print("analyzing '%P'\n", p); + switch(p->as) { + case ADATA: + case AGLOBL: + case ANAME: + case ASIGNAME: + case ATYPE: + continue; + } + checkprog(fn, p); + } +} + +// NOTE: The bitmap for a specific type t should be cached in t after the first run +// and then simply copied into bv at the correct offset on future calls with +// the same type t. On https://rsc.googlecode.com/hg/testdata/slow.go, twobitwalktype1 +// accounts for 40% of the 6g execution time. +static void +twobitwalktype1(Type *t, vlong *xoffset, Bvec *bv) +{ + vlong fieldoffset; + vlong i; + vlong o; + Type *t1; + + if(t->align > 0 && (*xoffset & (t->align - 1)) != 0) + fatal("twobitwalktype1: invalid initial alignment, %T", t); + + switch(t->etype) { + case TINT8: + case TUINT8: + case TINT16: + case TUINT16: + case TINT32: + case TUINT32: + case TINT64: + case TUINT64: + case TINT: + case TUINT: + case TUINTPTR: + case TBOOL: + case TFLOAT32: + case TFLOAT64: + case TCOMPLEX64: + case TCOMPLEX128: + for(i = 0; i < t->width; i++) { + bvset(bv, ((*xoffset + i) / widthptr) * BitsPerPointer); // 1 = live scalar + } + *xoffset += t->width; + break; + + case TPTR32: + case TPTR64: + case TUNSAFEPTR: + case TFUNC: + case TCHAN: + case TMAP: + if((*xoffset & (widthptr-1)) != 0) + fatal("twobitwalktype1: invalid alignment, %T", t); + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 2 = live ptr + *xoffset += t->width; + break; + + case TSTRING: + // struct { byte *str; intgo len; } + if((*xoffset & (widthptr-1)) != 0) + fatal("twobitwalktype1: invalid alignment, %T", t); + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 0); + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); // 3:0 = multiword:string + *xoffset += t->width; + break; + + case TINTER: + // struct { Itab *tab; union { void *ptr, uintptr val } data; } + // or, when isnilinter(t)==true: + // struct { Type *type; union { void *ptr, uintptr val } data; } + if((*xoffset & (widthptr-1)) != 0) + fatal("twobitwalktype1: invalid alignment, %T", t); + bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 0); + bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 1); // 3 = multiword + // next word contains 2 = Iface, 3 = Eface + if(isnilinter(t)) { + bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 2); + bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 3); + } else { + bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 3); + } + *xoffset += t->width; + break; + + case TARRAY: + // The value of t->bound is -1 for slices types and >0 for + // for fixed array types. All other values are invalid. + if(t->bound < -1) + fatal("twobitwalktype1: invalid bound, %T", t); + if(isslice(t)) { + // struct { byte *array; uintgo len; uintgo cap; } + if((*xoffset & (widthptr-1)) != 0) + fatal("twobitwalktype1: invalid TARRAY alignment, %T", t); + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 0); + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 1); + bvset(bv, (*xoffset / widthptr) * BitsPerPointer + 2); // 3:1 = multiword/slice + *xoffset += t->width; + } else + for(i = 0; i < t->bound; i++) + twobitwalktype1(t->type, xoffset, bv); + break; + + case TSTRUCT: + o = 0; + for(t1 = t->type; t1 != T; t1 = t1->down) { + fieldoffset = t1->width; + *xoffset += fieldoffset - o; + twobitwalktype1(t1->type, xoffset, bv); + o = fieldoffset + t1->type->width; + } + *xoffset += t->width - o; + break; + + default: + fatal("twobitwalktype1: unexpected type, %T", t); + } +} + +// Returns the number of words of local variables. +static int32 +localswords(void) +{ + return stkptrsize / widthptr; +} + +// Returns the number of words of in and out arguments. +static int32 +argswords(void) +{ + return curfn->type->argwid / widthptr; +} + +// Generates live pointer value maps for arguments and local variables. The +// this argument and the in arguments are always assumed live. The vars +// argument is an array of Node*s. +static void +twobitlivepointermap(Liveness *lv, Bvec *liveout, Array *vars, Bvec *args, Bvec *locals) +{ + Node *node; + Type *thisargtype; + Type *inargtype; + vlong xoffset; + int32 i; + + for(i = 0; i < arraylength(vars); i++) { + node = *(Node**)arrayget(vars, i); + switch(node->class) { + case PAUTO: + if(bvget(liveout, i)) { + xoffset = node->xoffset + stkptrsize; + twobitwalktype1(node->type, &xoffset, locals); + } + break; + case PPARAM: + case PPARAMOUT: + if(bvget(liveout, i)) { + xoffset = node->xoffset; + twobitwalktype1(node->type, &xoffset, args); + } + break; + } + } + + // The node list only contains declared names. + // If the receiver or arguments are unnamed, they will be omitted + // from the list above. Preserve those values - even though they are unused - + // in order to keep their addresses live for use in stack traces. + thisargtype = getthisx(lv->fn->type); + if(thisargtype != nil) { + xoffset = 0; + twobitwalktype1(thisargtype, &xoffset, args); + } + inargtype = getinargx(lv->fn->type); + if(inargtype != nil) { + xoffset = 0; + twobitwalktype1(inargtype, &xoffset, args); + } +} + +// Construct a disembodied instruction. +static Prog* +unlinkedprog(int as) +{ + Prog *p; + + p = mal(sizeof(*p)); + clearp(p); + p->as = as; + return p; +} + +// Construct a new PCDATA instruction associated with and for the purposes of +// covering an existing instruction. +static Prog* +newpcdataprog(Prog *prog, int32 index) +{ + Node from, to; + Prog *pcdata; + + nodconst(&from, types[TINT32], PCDATA_StackMapIndex); + nodconst(&to, types[TINT32], index); + pcdata = unlinkedprog(APCDATA); + pcdata->lineno = prog->lineno; + naddr(&from, &pcdata->from, 0); + naddr(&to, &pcdata->to, 0); + return pcdata; +} + +// Returns true for instructions that are safe points that must be annotated +// with liveness information. +static int +issafepoint(Prog *prog) +{ + return prog->as == ATEXT || prog->as == ACALL; +} + +// Initializes the sets for solving the live variables. Visits all the +// instructions in each basic block to summarizes the information at each basic +// block +static void +livenessprologue(Liveness *lv) +{ + BasicBlock *bb; + Bvec *uevar, *varkill, *avarinit; + Prog *p; + int32 i; + int32 nvars; + + 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(p = bb->last; p != nil; p = p->opt) { + progeffects(p, lv->vars, uevar, varkill, avarinit); + if(debuglive >= 3) + printeffects(p, 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); + } + // Walk the block instructions forward to update avarinit bits. + // avarinit describes the effect at the end of the block, not the beginning. + bvresetall(varkill); + for(p = bb->first;; p = p->link) { + progeffects(p, lv->vars, uevar, varkill, avarinit); + if(debuglive >= 3) + printeffects(p, uevar, varkill, avarinit); + bvandnot(lv->avarinit[i], lv->avarinit[i], varkill); + bvor(lv->avarinit[i], lv->avarinit[i], avarinit); + if(p == bb->last) + break; + } + } + free(uevar); + free(varkill); + free(avarinit); +} + +// Solve the liveness dataflow equations. +static void +livenesssolve(Liveness *lv) +{ + BasicBlock *bb, *succ, *pred; + Bvec *newlivein, *newliveout, *any, *all; + int32 rpo, i, j, change; + + // These temporary bitvectors exist to avoid successive allocations and + // 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 the block exit. + // avarinitany says the addressed var is initialized along some path reaching the block exit. + 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]); + } + bvcopy(lv->avarinitany[rpo], lv->avarinit[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]); + } + } + bvandnot(any, any, lv->varkill[rpo]); + bvandnot(all, all, lv->varkill[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 + // so low that it hardly seems to be worth the complexity. + change = 1; + while(change != 0) { + change = 0; + // Walk blocks in the general direction of propagation. This + // improves convergence. + for(i = arraylength(lv->cfg) - 1; i >= 0; i--) { + // A variable is live on output from this block + // if it is live on input to some successor. + // + // out[b] = \bigcup_{s \in succ[b]} in[s] + bb = *(BasicBlock**)arrayget(lv->cfg, i); + rpo = bb->rpo; + bvresetall(newliveout); + for(j = 0; j < arraylength(bb->succ); j++) { + succ = *(BasicBlock**)arrayget(bb->succ, j); + bvor(newliveout, newliveout, lv->livein[succ->rpo]); + } + if(bvcmp(lv->liveout[rpo], newliveout)) { + change = 1; + bvcopy(lv->liveout[rpo], newliveout); + } + + // A variable is live on input to this block + // if it is live on output from this block and + // not set by the code in this block. + // + // in[b] = uevar[b] \cup (out[b] \setminus varkill[b]) + bvandnot(newlivein, lv->liveout[rpo], lv->varkill[rpo]); + bvor(lv->livein[rpo], newlivein, lv->uevar[rpo]); + } + } + + free(newlivein); + free(newliveout); + free(any); + free(all); +} + +// This function is slow but it is only used for generating debug prints. +// Check whether n is marked live in args/locals. +static int +islive(Node *n, Bvec *args, Bvec *locals) +{ + int i; + + switch(n->class) { + case PPARAM: + case PPARAMOUT: + for(i = 0; i < n->type->width/widthptr*BitsPerPointer; i++) + if(bvget(args, n->xoffset/widthptr*BitsPerPointer + i)) + return 1; + break; + case PAUTO: + for(i = 0; i < n->type->width/widthptr*BitsPerPointer; i++) + if(bvget(locals, (n->xoffset + stkptrsize)/widthptr*BitsPerPointer + i)) + return 1; + break; + } + return 0; +} + +// Visits all instructions in a basic block and computes a bit vector of live +// variables at each safe point locations. +static void +livenessepilogue(Liveness *lv) +{ + BasicBlock *bb, *pred; + Bvec *ambig, *livein, *liveout, *uevar, *varkill, *args, *locals, *avarinit, *any, *all; + Node *n; + Prog *p, *next; + int32 i, j, numlive, startmsg, nmsg, nvars, pos; + vlong xoffset; + char **msg; + Fmt fmt; + + 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); + ambig = bvalloc(localswords() * BitsPerPointer); + msg = nil; + nmsg = 0; + startmsg = 0; + + for(i = 0; i < arraylength(lv->cfg); i++) { + bb = *(BasicBlock**)arrayget(lv->cfg, i); + + // Compute avarinitany and avarinitall for entry to block. + // This duplicates information known during livenesssolve + // but avoids storing two more vectors for each block. + 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 liveness maps for those instructions that need them. + // Seed the maps with information about the addrtaken variables. + for(p = bb->first;; p = p->link) { + progeffects(p, lv->vars, uevar, varkill, avarinit); + bvandnot(any, any, varkill); + bvandnot(all, all, varkill); + bvor(any, any, avarinit); + bvor(all, all, avarinit); + + if(issafepoint(p)) { + // Annotate ambiguously live variables so that they can + // be zeroed at function entry. + // livein and liveout are dead here and used as temporaries. + // For now, only enabled when using GOEXPERIMENT=precisestack + // during make.bash / all.bash. + if(precisestack_enabled) { + bvresetall(livein); + bvandnot(liveout, any, all); + if(!bvisempty(liveout)) { + for(pos = 0; pos < liveout->n; pos++) { + if(!bvget(liveout, pos)) + continue; + bvset(all, pos); // silence future warnings in this block + n = *(Node**)arrayget(lv->vars, pos); + if(!n->needzero) { + n->needzero = 1; + if(debuglive >= 1) + warnl(p->lineno, "%N: %lN is ambiguously live", curfn->nname, n); + // Record in 'ambiguous' bitmap. + xoffset = n->xoffset + stkptrsize; + twobitwalktype1(n->type, &xoffset, ambig); + } + } + } + } + + // 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(debuglive >= 3) { + print("%P\n", p); + printvars("avarinitany", any, lv->vars); + } + + // Record any values with an "address taken" reaching + // this code position as live. Must do now instead of below + // because the any/all calculation requires walking forward + // over the block (as this loop does), while the liveout + // requires walking backward (as the next loop does). + twobitlivepointermap(lv, any, lv->vars, args, locals); + } + + if(p == bb->last) + break; + } + bb->lastbitmapindex = arraylength(lv->livepointers) - 1; + } + + for(i = 0; i < arraylength(lv->cfg); i++) { + bb = *(BasicBlock**)arrayget(lv->cfg, i); + + if(debuglive >= 1 && strcmp(curfn->nname->sym->name, "init") != 0 && curfn->nname->sym->name[0] != '.') { + nmsg = arraylength(lv->livepointers); + startmsg = nmsg; + msg = xmalloc(nmsg*sizeof msg[0]); + for(j=0; j<nmsg; j++) + msg[j] = nil; + } + + // walk backward, emit pcdata and populate the maps + pos = bb->lastbitmapindex; + if(pos < 0) { + // the first block we encounter should have the ATEXT so + // 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 = next) { + next = p->opt; // splicebefore modifies p->opt + // Propagate liveness information + progeffects(p, lv->vars, uevar, varkill, avarinit); + bvcopy(liveout, livein); + bvandnot(livein, liveout, varkill); + bvor(livein, livein, uevar); + if(debuglive >= 3 && issafepoint(p)){ + print("%P\n", p); + printvars("uevar", uevar, lv->vars); + printvars("varkill", varkill, lv->vars); + printvars("livein", livein, lv->vars); + printvars("liveout", liveout, lv->vars); + } + if(issafepoint(p)) { + // Found an interesting instruction, record the + // corresponding liveness information. + + // Useful sanity check: on entry to the function, + // the only things that can possibly be live are the + // input parameters. + if(p->as == ATEXT) { + for(j = 0; j < liveout->n; j++) { + if(!bvget(liveout, j)) + continue; + n = *(Node**)arrayget(lv->vars, j); + if(n->class != PPARAM) + yyerrorl(p->lineno, "internal error: %N %lN recorded as live on entry", curfn->nname, n); + } + } + + // Record live pointers. + args = *(Bvec**)arrayget(lv->argslivepointers, pos); + locals = *(Bvec**)arrayget(lv->livepointers, pos); + twobitlivepointermap(lv, liveout, lv->vars, args, locals); + + // Ambiguously live variables are zeroed immediately after + // function entry. Mark them live for all the non-entry bitmaps + // so that GODEBUG=gcdead=1 mode does not poison them. + if(p->as == ACALL) + bvor(locals, locals, ambig); + + // Show live pointer bitmaps. + // We're interpreting the args and locals bitmap instead of liveout so that we + // include the bits added by the avarinit logic in the + // previous loop. + if(msg != nil) { + fmtstrinit(&fmt); + fmtprint(&fmt, "%L: live at ", p->lineno); + if(p->as == ACALL && p->to.node) + fmtprint(&fmt, "call to %s:", p->to.node->sym->name); + else if(p->as == ACALL) + fmtprint(&fmt, "indirect call:"); + else + fmtprint(&fmt, "entry to %s:", p->from.node->sym->name); + numlive = 0; + for(j = 0; j < arraylength(lv->vars); j++) { + n = *(Node**)arrayget(lv->vars, j); + if(islive(n, args, locals)) { + fmtprint(&fmt, " %N", n); + numlive++; + } + } + fmtprint(&fmt, "\n"); + if(numlive == 0) // squelch message + free(fmtstrflush(&fmt)); + else + msg[--startmsg] = fmtstrflush(&fmt); + } + + // Only CALL instructions need a PCDATA annotation. + // The TEXT instruction annotation is implicit. + if(p->as == ACALL) { + if(isdeferreturn(p)) { + // runtime.deferreturn modifies its return address to return + // back to the CALL, not to the subsequent instruction. + // Because the return comes back one instruction early, + // the PCDATA must begin one instruction early too. + // The instruction before a call to deferreturn is always a + // no-op, to keep PC-specific data unambiguous. + splicebefore(lv, bb, newpcdataprog(p->opt, pos), p->opt); + } else { + splicebefore(lv, bb, newpcdataprog(p, pos), p); + } + } + + pos--; + } + } + if(msg != nil) { + for(j=startmsg; j<nmsg; j++) + if(msg[j] != nil) + print("%s", msg[j]); + free(msg); + msg = nil; + nmsg = 0; + startmsg = 0; + } + } + + free(livein); + free(liveout); + free(uevar); + free(varkill); + free(avarinit); + free(any); + free(all); + free(ambig); + + flusherrors(); +} + +// FNV-1 hash function constants. +#define H0 2166136261UL +#define Hp 16777619UL + +static uint32 +hashbitmap(uint32 h, Bvec *bv) +{ + uchar *p, *ep; + + p = (uchar*)bv->b; + ep = p + 4*((bv->n+31)/32); + while(p < ep) + h = (h*Hp) ^ *p++; + return h; +} + +// Compact liveness information by coalescing identical per-call-site bitmaps. +// The merging only happens for a single function, not across the entire binary. +// +// There are actually two lists of bitmaps, one list for the local variables and one +// list for the function arguments. Both lists are indexed by the same PCDATA +// index, so the corresponding pairs must be considered together when +// merging duplicates. The argument bitmaps change much less often during +// function execution than the local variable bitmaps, so it is possible that +// we could introduce a separate PCDATA index for arguments vs locals and +// then compact the set of argument bitmaps separately from the set of +// local variable bitmaps. As of 2014-04-02, doing this to the godoc binary +// is actually a net loss: we save about 50k of argument bitmaps but the new +// PCDATA tables cost about 100k. So for now we keep using a single index for +// both bitmap lists. +static void +livenesscompact(Liveness *lv) +{ + int *table, *remap, i, j, n, tablesize, uniq; + uint32 h; + Bvec *local, *arg, *jlocal, *jarg; + Prog *p; + + // Linear probing hash table of bitmaps seen so far. + // The hash table has 4n entries to keep the linear + // scan short. An entry of -1 indicates an empty slot. + n = arraylength(lv->livepointers); + tablesize = 4*n; + table = xmalloc(tablesize*sizeof table[0]); + memset(table, 0xff, tablesize*sizeof table[0]); + + // remap[i] = the new index of the old bit vector #i. + remap = xmalloc(n*sizeof remap[0]); + memset(remap, 0xff, n*sizeof remap[0]); + uniq = 0; // unique tables found so far + + // Consider bit vectors in turn. + // If new, assign next number using uniq, + // record in remap, record in lv->livepointers and lv->argslivepointers + // under the new index, and add entry to hash table. + // If already seen, record earlier index in remap and free bitmaps. + for(i=0; i<n; i++) { + local = *(Bvec**)arrayget(lv->livepointers, i); + arg = *(Bvec**)arrayget(lv->argslivepointers, i); + h = hashbitmap(hashbitmap(H0, local), arg) % tablesize; + + for(;;) { + j = table[h]; + if(j < 0) + break; + jlocal = *(Bvec**)arrayget(lv->livepointers, j); + jarg = *(Bvec**)arrayget(lv->argslivepointers, j); + if(bvcmp(local, jlocal) == 0 && bvcmp(arg, jarg) == 0) { + free(local); + free(arg); + remap[i] = j; + goto Next; + } + if(++h == tablesize) + h = 0; + } + table[h] = uniq; + remap[i] = uniq; + *(Bvec**)arrayget(lv->livepointers, uniq) = local; + *(Bvec**)arrayget(lv->argslivepointers, uniq) = arg; + uniq++; + Next:; + } + + // We've already reordered lv->livepointers[0:uniq] + // and lv->argslivepointers[0:uniq] and freed the bitmaps + // we don't need anymore. Clear the pointers later in the + // array so that we can tell where the coalesced bitmaps stop + // and so that we don't double-free when cleaning up. + for(j=uniq; j<n; j++) { + *(Bvec**)arrayget(lv->livepointers, j) = nil; + *(Bvec**)arrayget(lv->argslivepointers, j) = nil; + } + + // Rewrite PCDATA instructions to use new numbering. + for(p=lv->ptxt; p != P; p=p->link) { + if(p->as == APCDATA && p->from.offset == PCDATA_StackMapIndex) { + i = p->to.offset; + if(i >= 0) + p->to.offset = remap[i]; + } + } + + free(table); + free(remap); +} + +static int +printbitset(int printed, char *name, Array *vars, Bvec *bits) +{ + int i, started; + Node *n; + + started = 0; + for(i=0; i<arraylength(vars); i++) { + if(!bvget(bits, i)) + continue; + if(!started) { + if(!printed) + print("\t"); + else + print(" "); + started = 1; + printed = 1; + print("%s=", name); + } else { + print(","); + } + n = *(Node**)arrayget(vars, i); + print("%s", n->sym->name); + } + return printed; +} + +// Prints the computed liveness information and inputs, for debugging. +// This format synthesizes the information used during the multiple passes +// into a single presentation. +static void +livenessprintdebug(Liveness *lv) +{ + int i, j, pcdata, printed; + BasicBlock *bb; + Prog *p; + Bvec *uevar, *varkill, *avarinit, *args, *locals; + Node *n; + + print("liveness: %s\n", curfn->nname->sym->name); + + uevar = bvalloc(arraylength(lv->vars)); + varkill = bvalloc(arraylength(lv->vars)); + avarinit = bvalloc(arraylength(lv->vars)); + + pcdata = 0; + for(i = 0; i < arraylength(lv->cfg); i++) { + if(i > 0) + print("\n"); + bb = *(BasicBlock**)arrayget(lv->cfg, i); + + // bb#0 pred=1,2 succ=3,4 + print("bb#%d pred=", i); + for(j = 0; j < arraylength(bb->pred); j++) { + if(j > 0) + print(","); + print("%d", (*(BasicBlock**)arrayget(bb->pred, j))->rpo); + } + print(" succ="); + for(j = 0; j < arraylength(bb->succ); j++) { + if(j > 0) + print(","); + print("%d", (*(BasicBlock**)arrayget(bb->succ, j))->rpo); + } + print("\n"); + + // initial settings + printed = 0; + printed = printbitset(printed, "uevar", lv->vars, lv->uevar[bb->rpo]); + printed = printbitset(printed, "livein", lv->vars, lv->livein[bb->rpo]); + if(printed) + print("\n"); + + // program listing, with individual effects listed + for(p = bb->first;; p = p->link) { + print("%P\n", p); + if(p->as == APCDATA && p->from.offset == PCDATA_StackMapIndex) + pcdata = p->to.offset; + progeffects(p, lv->vars, uevar, varkill, avarinit); + printed = 0; + printed = printbitset(printed, "uevar", lv->vars, uevar); + printed = printbitset(printed, "varkill", lv->vars, varkill); + printed = printbitset(printed, "avarinit", lv->vars, avarinit); + if(printed) + print("\n"); + if(issafepoint(p)) { + args = *(Bvec**)arrayget(lv->argslivepointers, pcdata); + locals = *(Bvec**)arrayget(lv->livepointers, pcdata); + print("\tlive="); + printed = 0; + for(j = 0; j < arraylength(lv->vars); j++) { + n = *(Node**)arrayget(lv->vars, j); + if(islive(n, args, locals)) { + if(printed++) + print(","); + print("%N", n); + } + } + print("\n"); + } + if(p == bb->last) + break; + } + + // bb bitsets + print("end\n"); + printed = printbitset(printed, "varkill", lv->vars, lv->varkill[bb->rpo]); + printed = printbitset(printed, "liveout", lv->vars, lv->liveout[bb->rpo]); + printed = printbitset(printed, "avarinit", lv->vars, lv->avarinit[bb->rpo]); + printed = printbitset(printed, "avarinitany", lv->vars, lv->avarinitany[bb->rpo]); + printed = printbitset(printed, "avarinitall", lv->vars, lv->avarinitall[bb->rpo]); + if(printed) + print("\n"); + } + print("\n"); + + free(uevar); + free(varkill); + free(avarinit); +} + +// Dumps an array of bitmaps to a symbol as a sequence of uint32 values. The +// first word dumped is the total number of bitmaps. The second word is the +// length of the bitmaps. All bitmaps are assumed to be of equal length. The +// words that are followed are the raw bitmap words. The arr argument is an +// array of Node*s. +static void +twobitwritesymbol(Array *arr, Sym *sym) +{ + Bvec *bv; + int off, i, j, len; + uint32 word; + + len = arraylength(arr); + off = 0; + off += 4; // number of bitmaps, to fill in later + bv = *(Bvec**)arrayget(arr, 0); + off = duint32(sym, off, bv->n); // number of bits in each bitmap + for(i = 0; i < len; i++) { + // bitmap words + bv = *(Bvec**)arrayget(arr, i); + if(bv == nil) + break; + for(j = 0; j < bv->n; j += 32) { + word = bv->b[j/32]; + off = duint32(sym, off, word); + } + } + duint32(sym, 0, i); // number of bitmaps + ggloblsym(sym, off, 0, 1); +} + +static void +printprog(Prog *p) +{ + while(p != nil) { + print("%P\n", p); + p = p->link; + } +} + +// Entry pointer for liveness analysis. Constructs a complete CFG, solves for +// the liveness of pointer variables in the function, and emits a runtime data +// structure read by the garbage collector. +void +liveness(Node *fn, Prog *firstp, Sym *argssym, Sym *livesym) +{ + Array *cfg, *vars; + Liveness *lv; + int debugdelta; + + // Change name to dump debugging information only for a specific function. + debugdelta = 0; + if(strcmp(curfn->nname->sym->name, "!") == 0) + debugdelta = 2; + + debuglive += debugdelta; + if(debuglive >= 3) { + print("liveness: %s\n", curfn->nname->sym->name); + printprog(firstp); + } + checkptxt(fn, firstp); + + // Construct the global liveness state. + cfg = newcfg(firstp); + if(debuglive >= 3) + printcfg(cfg); + vars = getvariables(fn); + lv = newliveness(fn, firstp, cfg, vars); + + // Run the dataflow framework. + livenessprologue(lv); + if(debuglive >= 3) + livenessprintcfg(lv); + livenesssolve(lv); + if(debuglive >= 3) + livenessprintcfg(lv); + livenessepilogue(lv); + if(debuglive >= 3) + livenessprintcfg(lv); + livenesscompact(lv); + + if(debuglive >= 2) + livenessprintdebug(lv); + + // Emit the live pointer map data structures + twobitwritesymbol(lv->livepointers, livesym); + twobitwritesymbol(lv->argslivepointers, argssym); + + // Free everything. + freeliveness(lv); + arrayfree(vars); + freecfg(cfg); + + debuglive -= debugdelta; +} |